Solutions are presented as using the least memory and the fastest execution time. It also takes the top
10 most recent solutions from each language. If you want to limit to a specific index, click the
"Solved" button and go to that problem.
Problems
Recently, you received a rare ticket to the only casino in the world where you can actually earn something, and you want to take full advantage of this opportunity. The conditions in this casino are as follows: There are a total of (n) games in the casino. You can play each game at most once . Each game is characterized by two parameters: (p_i) ((1 \le p_i \le 100)) and (w_i) — the probability of winning the game in percentage and the winnings for a win. If you lose in any game you decide to play, you will receive nothing at all (even for the games you won). You need to choose a set of games in advance that you will play in such a way as to maximize the expected value of your winnings. In this case, if you choose to play the games with indices (i_1 < i_2 < \ldots < i_k), you will win in all of them with a probability of (\prod\limits_{j=1}^k \frac{p_{i_j}}{100}), and in that case, your winnings will be equal to (\sum\limits_{j=1}^k w_{i_j}). That is, the expected value of your winnings will be (\left(\prod\limits_{j=1}^k \frac{p_{i_j}}{100}\right) \cdot \left(\sum\limits_{j=1}^k w_{i_j}\right)). To avoid going bankrupt, the casino owners have limited the expected value of winnings for each individual game. Thus, for all (i) ((1 \le i \le n)), it holds that (w_i \cdot p_i \le 2 \cdot 10^5). Your task is to find the maximum expected value of winnings that can be obtained by choosing some set of games in the casino. The first line contains a single integer (n) ((1 \le n \le 2 \cdot 10^5)) — the number of games offered to play. The (i)-th of the following (n) lines contains two integers (p_i) and (w_i) ((1 \leq p_i \leq 100), (1 \leq w_i, p_i \cdot w_i \leq 2 \cdot 10^5)) — the probability of winning and the size of the winnings in the (i)-th game. Output a single number — the maximum expected value of winnings in the casino that can be obtained by choosing some subset of games. Yo |
Tutorials
Submissions
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
|
287006996 |
hos.lyric |
D |
Oct. 20, 2024, 10:47 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
171 |
4710400 |
|
|
|
287033241 |
qwef_ |
D |
Oct. 20, 2024, noon |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
202 |
22528000 |
|
|
|
287004665 |
oleh1421 |
D |
Oct. 20, 2024, 10:42 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
217 |
80179200 |
|
|
|
287000155 |
Morphymorphymorphy |
D |
Oct. 20, 2024, 10:33 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
218 |
13721600 |
|
|
|
287001599 |
244mhq |
D |
Oct. 20, 2024, 10:36 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
233 |
11059200 |
|
|
|
287010890 |
Noam527 |
D |
Oct. 20, 2024, 10:55 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
328 |
13516800 |
|
|
|
287133270 |
larsr |
D |
Oct. 21, 2024, 12:39 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
468 |
4300800 |
|
|
|
287060205 |
black_third |
D |
Oct. 20, 2024, 12:35 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
531 |
12083200 |
|
|
|
287133353 |
songke123 |
D |
Oct. 21, 2024, 12:41 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
546 |
1638400 |
|
|
|
287132705 |
songke123 |
D |
Oct. 21, 2024, 12:23 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
86 |
593 |
3276800 |
|
|
|
287110313 |
EJIC_B_KEDAX |
D |
Oct. 20, 2024, 6:38 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
124 |
9011200 |
|
|
|
287009498 |
Karuna |
D |
Oct. 20, 2024, 10:52 a.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
140 |
3174400 |
|
|
|
287110522 |
EJIC_B_KEDAX |
D |
Oct. 20, 2024, 6:40 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
140 |
6451200 |
|
|
|
287110975 |
EJIC_B_KEDAX |
D |
Oct. 20, 2024, 6:44 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
140 |
6758400 |
|
|
|
287110464 |
EJIC_B_KEDAX |
D |
Oct. 20, 2024, 6:39 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
140 |
7065600 |
|
|
|
287111150 |
EJIC_B_KEDAX |
D |
Oct. 20, 2024, 6:45 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
140 |
7577600 |
|
|
|
287110600 |
EJIC_B_KEDAX |
D |
Oct. 20, 2024, 6:40 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
140 |
8192000 |
|
|
|
287110763 |
EJIC_B_KEDAX |
D |
Oct. 20, 2024, 6:42 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
140 |
8396800 |
|
|
|
287111275 |
EJIC_B_KEDAX |
D |
Oct. 20, 2024, 6:46 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
155 |
5017600 |
|
|
|
286996222 |
CJ-_zhuyifan |
D |
Oct. 20, 2024, 10:26 a.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
86 |
155 |
118272000 |
|
|
|
287010357 |
cmk666 |
D |
Oct. 20, 2024, 10:54 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
124 |
5836800 |
|
|
|
286972363 |
Kevin114514 |
D |
Oct. 20, 2024, 9:55 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
218 |
6963200 |
|
|
|
286984453 |
Sugar_fan |
D |
Oct. 20, 2024, 10:04 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
233 |
11264000 |
|
|
|
286991730 |
skip2004 |
D |
Oct. 20, 2024, 10:17 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
249 |
3584000 |
|
|
|
287071680 |
Benq |
D |
Oct. 20, 2024, 1:48 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
265 |
5222400 |
|
|
|
287144254 |
xlk |
D |
Oct. 21, 2024, 4:15 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
327 |
1638400 |
|
|
|
287146176 |
Dominater069 |
D |
Oct. 21, 2024, 4:40 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
327 |
5017600 |
|
|
|
287015290 |
Kite_kuma |
D |
Oct. 20, 2024, 11:03 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
421 |
9728000 |
|
|
|
287149745 |
Marckess |
D |
Oct. 21, 2024, 5:26 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
467 |
5427200 |
|
|
|
287072869 |
Suwan |
D |
Oct. 20, 2024, 1:56 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
86 |
671 |
16076800 |
|
|
|
287083187 |
yvbf |
D |
Oct. 20, 2024, 3:10 p.m. |
OK |
Java 8 |
TESTS |
86 |
1108 |
5939200 |
|
|
|
287067061 |
PNJ0714 |
D |
Oct. 20, 2024, 1:17 p.m. |
OK |
PyPy 3-64 |
TESTS |
86 |
843 |
11878400 |
|
|
|
287044053 |
sansen |
D |
Oct. 20, 2024, 12:16 p.m. |
OK |
Rust 2021 |
TESTS |
86 |
109 |
9728000 |
|
|
|
287044078 |
sansen |
D |
Oct. 20, 2024, 12:16 p.m. |
OK |
Rust 2021 |
TESTS |
86 |
124 |
5939200 |
|
|
|
287042805 |
sansen |
D |
Oct. 20, 2024, 12:09 p.m. |
OK |
Rust 2021 |
TESTS |
86 |
156 |
8396800 |
|
|
remove filters
Back to search problems