oj.uz

Submission #631195

# Submission time Handle Problem Language Result Execution time Memory
631195 2022-08-17T19:30:12 Z Ooops_sorry Let's Win the Election (JOI22_ho_t3) C++17
100 / 100
 1673 ms 1038836 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(51);

#define ll long long
#define pb push_back
#define ld double

const int N = 510, INF = 1e9;
int a[N], b[N], n, k;
ld dp[N][N][N];
vector<int> ord;

ld solve(int cnt) {
    dp[0][0][1] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (i == j) {
                for (int k = 1; k <= i + 1; k++) {
                    dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
                    dp[i + 1][j + 1][k + 1] = min(dp[i + 1][j + 1][k + 1], dp[i][j][k] + (ld)b[ord[i]] / (ld)k);
                    dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] + (ld)a[ord[i]] / (ld)cnt);
                }
            } else {
                dp[i + 1][j][cnt] = min(dp[i + 1][j][cnt], dp[i][j][cnt]);
                dp[i + 1][j + 1][cnt] = min(dp[i + 1][j + 1][cnt], dp[i][j][cnt] + (ld)a[ord[i]] / (ld)cnt);
            }
        }
    }
    return dp[n][k][cnt];
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                dp[i][j][k] = INF;
            }
        }
    }
    cin >> n >> k;
    ord.resize(n);
    iota(ord.begin(), ord.end(), 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        if (b[i] == -1) {
            b[i] = INF;
        }
    }
    sort(ord.begin(), ord.end(), [&](int i, int j){return b[i] < b[j] || (b[i] == b[j] && a[i] < a[j]);});
    ld ans = INF;
    for (int i = 1; i <= k + 1; i++) {
        ans = min(ans, solve(i));
    }
    cout << setprecision(30) << fixed << ans << endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 1038632 KB Output is correct
2 Correct 408 ms 1038644 KB Output is correct
3 Correct 387 ms 1038636 KB Output is correct
4 Correct 387 ms 1038616 KB Output is correct
5 Correct 493 ms 1038596 KB Output is correct
6 Correct 686 ms 1038608 KB Output is correct
7 Correct 949 ms 1038792 KB Output is correct
8 Correct 1194 ms 1038676 KB Output is correct
9 Correct 1413 ms 1038672 KB Output is correct
10 Correct 1091 ms 1038680 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 1038632 KB Output is correct
2 Correct 408 ms 1038644 KB Output is correct
3 Correct 387 ms 1038636 KB Output is correct
4 Correct 387 ms 1038616 KB Output is correct
5 Correct 493 ms 1038596 KB Output is correct
6 Correct 686 ms 1038608 KB Output is correct
7 Correct 949 ms 1038792 KB Output is correct
8 Correct 1194 ms 1038676 KB Output is correct
9 Correct 1413 ms 1038672 KB Output is correct
10 Correct 1091 ms 1038680 KB Output is correct
11 Correct 395 ms 1038624 KB Output is correct
12 Correct 716 ms 1038676 KB Output is correct
13 Correct 688 ms 1038712 KB Output is correct
14 Correct 707 ms 1038612 KB Output is correct
15 Correct 1143 ms 1038584 KB Output is correct
16 Correct 1111 ms 1038712 KB Output is correct
17 Correct 1133 ms 1038704 KB Output is correct
18 Correct 1534 ms 1038672 KB Output is correct
19 Correct 1673 ms 1038672 KB Output is correct
20 Correct 1422 ms 1038784 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 1038612 KB Output is correct
2 Correct 392 ms 1038824 KB Output is correct
3 Correct 396 ms 1038636 KB Output is correct
4 Correct 395 ms 1038704 KB Output is correct
5 Correct 401 ms 1038596 KB Output is correct
6 Correct 396 ms 1038560 KB Output is correct
7 Correct 418 ms 1038656 KB Output is correct
8 Correct 400 ms 1038836 KB Output is correct
9 Correct 432 ms 1038680 KB Output is correct
10 Correct 392 ms 1038568 KB Output is correct
11 Correct 391 ms 1038668 KB Output is correct
12 Correct 398 ms 1038552 KB Output is correct
13 Correct 391 ms 1038568 KB Output is correct
14 Correct 394 ms 1038552 KB Output is correct
15 Correct 384 ms 1038668 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 1038612 KB Output is correct
2 Correct 392 ms 1038824 KB Output is correct
3 Correct 396 ms 1038636 KB Output is correct
4 Correct 395 ms 1038704 KB Output is correct
5 Correct 401 ms 1038596 KB Output is correct
6 Correct 396 ms 1038560 KB Output is correct
7 Correct 418 ms 1038656 KB Output is correct
8 Correct 400 ms 1038836 KB Output is correct
9 Correct 432 ms 1038680 KB Output is correct
10 Correct 392 ms 1038568 KB Output is correct
11 Correct 391 ms 1038668 KB Output is correct
12 Correct 398 ms 1038552 KB Output is correct
13 Correct 391 ms 1038568 KB Output is correct
14 Correct 394 ms 1038552 KB Output is correct
15 Correct 384 ms 1038668 KB Output is correct
16 Correct 397 ms 1038668 KB Output is correct
17 Correct 389 ms 1038544 KB Output is correct
18 Correct 431 ms 1038668 KB Output is correct
19 Correct 392 ms 1038592 KB Output is correct
20 Correct 396 ms 1038576 KB Output is correct
21 Correct 401 ms 1038604 KB Output is correct
22 Correct 389 ms 1038668 KB Output is correct
23 Correct 405 ms 1038584 KB Output is correct
24 Correct 386 ms 1038640 KB Output is correct
25 Correct 404 ms 1038644 KB Output is correct
26 Correct 382 ms 1038668 KB Output is correct
27 Correct 409 ms 1038572 KB Output is correct
28 Correct 388 ms 1038584 KB Output is correct
29 Correct 426 ms 1038600 KB Output is correct
30 Correct 395 ms 1038588 KB Output is correct
31 Correct 424 ms 1038752 KB Output is correct
32 Correct 391 ms 1038548 KB Output is correct
33 Correct 400 ms 1038700 KB Output is correct
34 Correct 419 ms 1038556 KB Output is correct
35 Correct 409 ms 1038656 KB Output is correct
36 Correct 394 ms 1038604 KB Output is correct
37 Correct 396 ms 1038756 KB Output is correct
38 Correct 418 ms 1038552 KB Output is correct
39 Correct 394 ms 1038632 KB Output is correct
40 Correct 412 ms 1038660 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 1038612 KB Output is correct
2 Correct 392 ms 1038824 KB Output is correct
3 Correct 396 ms 1038636 KB Output is correct
4 Correct 395 ms 1038704 KB Output is correct
5 Correct 401 ms 1038596 KB Output is correct
6 Correct 396 ms 1038560 KB Output is correct
7 Correct 418 ms 1038656 KB Output is correct
8 Correct 400 ms 1038836 KB Output is correct
9 Correct 432 ms 1038680 KB Output is correct
10 Correct 392 ms 1038568 KB Output is correct
11 Correct 391 ms 1038668 KB Output is correct
12 Correct 398 ms 1038552 KB Output is correct
13 Correct 391 ms 1038568 KB Output is correct
14 Correct 394 ms 1038552 KB Output is correct
15 Correct 384 ms 1038668 KB Output is correct
16 Correct 397 ms 1038668 KB Output is correct
17 Correct 389 ms 1038544 KB Output is correct
18 Correct 431 ms 1038668 KB Output is correct
19 Correct 392 ms 1038592 KB Output is correct
20 Correct 396 ms 1038576 KB Output is correct
21 Correct 401 ms 1038604 KB Output is correct
22 Correct 389 ms 1038668 KB Output is correct
23 Correct 405 ms 1038584 KB Output is correct
24 Correct 386 ms 1038640 KB Output is correct
25 Correct 404 ms 1038644 KB Output is correct
26 Correct 382 ms 1038668 KB Output is correct
27 Correct 409 ms 1038572 KB Output is correct
28 Correct 388 ms 1038584 KB Output is correct
29 Correct 426 ms 1038600 KB Output is correct
30 Correct 395 ms 1038588 KB Output is correct
31 Correct 424 ms 1038752 KB Output is correct
32 Correct 391 ms 1038548 KB Output is correct
33 Correct 400 ms 1038700 KB Output is correct
34 Correct 419 ms 1038556 KB Output is correct
35 Correct 409 ms 1038656 KB Output is correct
36 Correct 394 ms 1038604 KB Output is correct
37 Correct 396 ms 1038756 KB Output is correct
38 Correct 418 ms 1038552 KB Output is correct
39 Correct 394 ms 1038632 KB Output is correct
40 Correct 412 ms 1038660 KB Output is correct
41 Correct 400 ms 1038716 KB Output is correct
42 Correct 401 ms 1038664 KB Output is correct
43 Correct 400 ms 1038616 KB Output is correct
44 Correct 385 ms 1038612 KB Output is correct
45 Correct 412 ms 1038664 KB Output is correct
46 Correct 393 ms 1038552 KB Output is correct
47 Correct 418 ms 1038632 KB Output is correct
48 Correct 397 ms 1038668 KB Output is correct
49 Correct 392 ms 1038784 KB Output is correct
50 Correct 409 ms 1038796 KB Output is correct
51 Correct 390 ms 1038632 KB Output is correct
52 Correct 407 ms 1038672 KB Output is correct
53 Correct 404 ms 1038668 KB Output is correct
54 Correct 396 ms 1038644 KB Output is correct
55 Correct 397 ms 1038584 KB Output is correct
56 Correct 399 ms 1038664 KB Output is correct
57 Correct 399 ms 1038652 KB Output is correct
58 Correct 395 ms 1038668 KB Output is correct
59 Correct 483 ms 1038564 KB Output is correct
60 Correct 405 ms 1038728 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 1038712 KB Output is correct
2 Correct 1453 ms 1038676 KB Output is correct
3 Correct 1424 ms 1038676 KB Output is correct
4 Correct 1410 ms 1038736 KB Output is correct
5 Correct 1441 ms 1038772 KB Output is correct
6 Correct 1399 ms 1038676 KB Output is correct
7 Correct 1413 ms 1038720 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 1038632 KB Output is correct
2 Correct 408 ms 1038644 KB Output is correct
3 Correct 387 ms 1038636 KB Output is correct
4 Correct 387 ms 1038616 KB Output is correct
5 Correct 493 ms 1038596 KB Output is correct
6 Correct 686 ms 1038608 KB Output is correct
7 Correct 949 ms 1038792 KB Output is correct
8 Correct 1194 ms 1038676 KB Output is correct
9 Correct 1413 ms 1038672 KB Output is correct
10 Correct 1091 ms 1038680 KB Output is correct
11 Correct 395 ms 1038624 KB Output is correct
12 Correct 716 ms 1038676 KB Output is correct
13 Correct 688 ms 1038712 KB Output is correct
14 Correct 707 ms 1038612 KB Output is correct
15 Correct 1143 ms 1038584 KB Output is correct
16 Correct 1111 ms 1038712 KB Output is correct
17 Correct 1133 ms 1038704 KB Output is correct
18 Correct 1534 ms 1038672 KB Output is correct
19 Correct 1673 ms 1038672 KB Output is correct
20 Correct 1422 ms 1038784 KB Output is correct
21 Correct 391 ms 1038612 KB Output is correct
22 Correct 392 ms 1038824 KB Output is correct
23 Correct 396 ms 1038636 KB Output is correct
24 Correct 395 ms 1038704 KB Output is correct
25 Correct 401 ms 1038596 KB Output is correct
26 Correct 396 ms 1038560 KB Output is correct
27 Correct 418 ms 1038656 KB Output is correct
28 Correct 400 ms 1038836 KB Output is correct
29 Correct 432 ms 1038680 KB Output is correct
30 Correct 392 ms 1038568 KB Output is correct
31 Correct 391 ms 1038668 KB Output is correct
32 Correct 398 ms 1038552 KB Output is correct
33 Correct 391 ms 1038568 KB Output is correct
34 Correct 394 ms 1038552 KB Output is correct
35 Correct 384 ms 1038668 KB Output is correct
36 Correct 397 ms 1038668 KB Output is correct
37 Correct 389 ms 1038544 KB Output is correct
38 Correct 431 ms 1038668 KB Output is correct
39 Correct 392 ms 1038592 KB Output is correct
40 Correct 396 ms 1038576 KB Output is correct
41 Correct 401 ms 1038604 KB Output is correct
42 Correct 389 ms 1038668 KB Output is correct
43 Correct 405 ms 1038584 KB Output is correct
44 Correct 386 ms 1038640 KB Output is correct
45 Correct 404 ms 1038644 KB Output is correct
46 Correct 382 ms 1038668 KB Output is correct
47 Correct 409 ms 1038572 KB Output is correct
48 Correct 388 ms 1038584 KB Output is correct
49 Correct 426 ms 1038600 KB Output is correct
50 Correct 395 ms 1038588 KB Output is correct
51 Correct 424 ms 1038752 KB Output is correct
52 Correct 391 ms 1038548 KB Output is correct
53 Correct 400 ms 1038700 KB Output is correct
54 Correct 419 ms 1038556 KB Output is correct
55 Correct 409 ms 1038656 KB Output is correct
56 Correct 394 ms 1038604 KB Output is correct
57 Correct 396 ms 1038756 KB Output is correct
58 Correct 418 ms 1038552 KB Output is correct
59 Correct 394 ms 1038632 KB Output is correct
60 Correct 412 ms 1038660 KB Output is correct
61 Correct 400 ms 1038716 KB Output is correct
62 Correct 401 ms 1038664 KB Output is correct
63 Correct 400 ms 1038616 KB Output is correct
64 Correct 385 ms 1038612 KB Output is correct
65 Correct 412 ms 1038664 KB Output is correct
66 Correct 393 ms 1038552 KB Output is correct
67 Correct 418 ms 1038632 KB Output is correct
68 Correct 397 ms 1038668 KB Output is correct
69 Correct 392 ms 1038784 KB Output is correct
70 Correct 409 ms 1038796 KB Output is correct
71 Correct 390 ms 1038632 KB Output is correct
72 Correct 407 ms 1038672 KB Output is correct
73 Correct 404 ms 1038668 KB Output is correct
74 Correct 396 ms 1038644 KB Output is correct
75 Correct 397 ms 1038584 KB Output is correct
76 Correct 399 ms 1038664 KB Output is correct
77 Correct 399 ms 1038652 KB Output is correct
78 Correct 395 ms 1038668 KB Output is correct
79 Correct 483 ms 1038564 KB Output is correct
80 Correct 405 ms 1038728 KB Output is correct
81 Correct 1440 ms 1038712 KB Output is correct
82 Correct 1453 ms 1038676 KB Output is correct
83 Correct 1424 ms 1038676 KB Output is correct
84 Correct 1410 ms 1038736 KB Output is correct
85 Correct 1441 ms 1038772 KB Output is correct
86 Correct 1399 ms 1038676 KB Output is correct
87 Correct 1413 ms 1038720 KB Output is correct
88 Correct 509 ms 1038668 KB Output is correct
89 Correct 511 ms 1038676 KB Output is correct
90 Correct 679 ms 1038672 KB Output is correct
91 Correct 693 ms 1038696 KB Output is correct
92 Correct 999 ms 1038756 KB Output is correct
93 Correct 909 ms 1038676 KB Output is correct
94 Correct 1151 ms 1038680 KB Output is correct
95 Correct 1197 ms 1038688 KB Output is correct
96 Correct 1311 ms 1038796 KB Output is correct
97 Correct 1437 ms 1038796 KB Output is correct
98 Correct 1086 ms 1038752 KB Output is correct
99 Correct 1161 ms 1038668 KB Output is correct
100 Correct 1156 ms 1038680 KB Output is correct
101 Correct 1203 ms 1038676 KB Output is correct
102 Correct 1262 ms 1038672 KB Output is correct
103 Correct 1366 ms 1038680 KB Output is correct
104 Correct 1462 ms 1038632 KB Output is correct
105 Correct 1139 ms 1038672 KB Output is correct