oj.uz

Submission #635379

# Submission time Handle Problem Language Result Execution time Memory
635379 2022-08-26T07:27:05 Z Astrayt Let's Win the Election (JOI22_ho_t3) C++17
100 / 100
 1460 ms 1018624 KB 
//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
//#define N 100005

void solve(){
    int N, K, cnt = 0; cin >> N >> K;
    vector<vector<vector<double>>> dp(505, vector<vector<double>>(505, vector<double>(505, 0)));
    double ans = 1e18;
    vector<pii> v(N + 1, pii(0, 0));
    for(int i = 1; i <= N; ++i){
        auto &[a, b] = v[i];
        cin >> a >> b;
        if(b != -1) ++cnt;
        else b = 1e18;
    }
    sort(v.begin(), v.end(), [](pii a, pii b){return a.ss < b.ss;});
    for(int goal = 0; goal <= min(K, cnt); ++goal){
        for(int i = 0; i <= N; ++i){
            for(int j = 0; j <= min(i, K); ++j){
                if(i == j){
                    for(int k = 0; k <= min(j, goal); ++k){
                        dp[i][j][k] = 1e18;
                    }
                }
                else dp[i][j][goal] = 1e18;
            }
        }
        dp[0][0][0] = 0;
        for(int i = 0; i < N; ++i){
            for(int j = max(0ll, K - N + i); j <= min(i, K); ++j){
                if(i == j){
                    for(int k = max(0ll, goal - N + i); k <= min(j, goal); ++k){
                        dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
                        dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] + 1.0 * v[i + 1].ff / (goal + 1));
                        dp[i + 1][j + 1][k + 1] = min(dp[i + 1][j + 1][k + 1], dp[i][j][k] + 1.0 * v[i + 1].ss / (k + 1));
                    }
                }else{
                    dp[i + 1][j][goal] = min(dp[i + 1][j][goal], dp[i][j][goal]);
                    dp[i + 1][j + 1][goal] = min(dp[i + 1][j + 1][goal], dp[i][j][goal] + 1.0 * v[i + 1].ff / (goal + 1));
                }
            }
        }
        ans = min(ans, dp[N][K][goal]);
    }
    cout << fixed << setprecision(9) << ans << '\n';
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1018500 KB Output is correct
2 Correct 439 ms 1018316 KB Output is correct
3 Correct 398 ms 1018392 KB Output is correct
4 Correct 404 ms 1018316 KB Output is correct
5 Correct 400 ms 1018524 KB Output is correct
6 Correct 409 ms 1018344 KB Output is correct
7 Correct 445 ms 1018392 KB Output is correct
8 Correct 417 ms 1018444 KB Output is correct
9 Correct 404 ms 1018372 KB Output is correct
10 Correct 396 ms 1018444 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1018500 KB Output is correct
2 Correct 439 ms 1018316 KB Output is correct
3 Correct 398 ms 1018392 KB Output is correct
4 Correct 404 ms 1018316 KB Output is correct
5 Correct 400 ms 1018524 KB Output is correct
6 Correct 409 ms 1018344 KB Output is correct
7 Correct 445 ms 1018392 KB Output is correct
8 Correct 417 ms 1018444 KB Output is correct
9 Correct 404 ms 1018372 KB Output is correct
10 Correct 396 ms 1018444 KB Output is correct
11 Correct 444 ms 1018480 KB Output is correct
12 Correct 626 ms 1018348 KB Output is correct
13 Correct 625 ms 1018340 KB Output is correct
14 Correct 627 ms 1018524 KB Output is correct
15 Correct 1386 ms 1018440 KB Output is correct
16 Correct 1158 ms 1018540 KB Output is correct
17 Correct 714 ms 1018444 KB Output is correct
18 Correct 1460 ms 1018568 KB Output is correct
19 Correct 1049 ms 1018444 KB Output is correct
20 Correct 579 ms 1018616 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 1018412 KB Output is correct
2 Correct 386 ms 1018424 KB Output is correct
3 Correct 407 ms 1018448 KB Output is correct
4 Correct 411 ms 1018424 KB Output is correct
5 Correct 436 ms 1018548 KB Output is correct
6 Correct 391 ms 1018312 KB Output is correct
7 Correct 438 ms 1018340 KB Output is correct
8 Correct 414 ms 1018320 KB Output is correct
9 Correct 452 ms 1018460 KB Output is correct
10 Correct 387 ms 1018348 KB Output is correct
11 Correct 448 ms 1018440 KB Output is correct
12 Correct 392 ms 1018404 KB Output is correct
13 Correct 443 ms 1018432 KB Output is correct
14 Correct 410 ms 1018316 KB Output is correct
15 Correct 407 ms 1018344 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 1018412 KB Output is correct
2 Correct 386 ms 1018424 KB Output is correct
3 Correct 407 ms 1018448 KB Output is correct
4 Correct 411 ms 1018424 KB Output is correct
5 Correct 436 ms 1018548 KB Output is correct
6 Correct 391 ms 1018312 KB Output is correct
7 Correct 438 ms 1018340 KB Output is correct
8 Correct 414 ms 1018320 KB Output is correct
9 Correct 452 ms 1018460 KB Output is correct
10 Correct 387 ms 1018348 KB Output is correct
11 Correct 448 ms 1018440 KB Output is correct
12 Correct 392 ms 1018404 KB Output is correct
13 Correct 443 ms 1018432 KB Output is correct
14 Correct 410 ms 1018316 KB Output is correct
15 Correct 407 ms 1018344 KB Output is correct
16 Correct 408 ms 1018420 KB Output is correct
17 Correct 408 ms 1018496 KB Output is correct
18 Correct 427 ms 1018416 KB Output is correct
19 Correct 429 ms 1018472 KB Output is correct
20 Correct 411 ms 1018360 KB Output is correct
21 Correct 403 ms 1018464 KB Output is correct
22 Correct 391 ms 1018432 KB Output is correct
23 Correct 408 ms 1018408 KB Output is correct
24 Correct 391 ms 1018316 KB Output is correct
25 Correct 449 ms 1018336 KB Output is correct
26 Correct 388 ms 1018464 KB Output is correct
27 Correct 439 ms 1018424 KB Output is correct
28 Correct 405 ms 1018540 KB Output is correct
29 Correct 440 ms 1018396 KB Output is correct
30 Correct 415 ms 1018356 KB Output is correct
31 Correct 399 ms 1018448 KB Output is correct
32 Correct 402 ms 1018384 KB Output is correct
33 Correct 436 ms 1018412 KB Output is correct
34 Correct 402 ms 1018352 KB Output is correct
35 Correct 399 ms 1018388 KB Output is correct
36 Correct 385 ms 1018408 KB Output is correct
37 Correct 391 ms 1018376 KB Output is correct
38 Correct 388 ms 1018380 KB Output is correct
39 Correct 392 ms 1018360 KB Output is correct
40 Correct 449 ms 1018316 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 1018412 KB Output is correct
2 Correct 386 ms 1018424 KB Output is correct
3 Correct 407 ms 1018448 KB Output is correct
4 Correct 411 ms 1018424 KB Output is correct
5 Correct 436 ms 1018548 KB Output is correct
6 Correct 391 ms 1018312 KB Output is correct
7 Correct 438 ms 1018340 KB Output is correct
8 Correct 414 ms 1018320 KB Output is correct
9 Correct 452 ms 1018460 KB Output is correct
10 Correct 387 ms 1018348 KB Output is correct
11 Correct 448 ms 1018440 KB Output is correct
12 Correct 392 ms 1018404 KB Output is correct
13 Correct 443 ms 1018432 KB Output is correct
14 Correct 410 ms 1018316 KB Output is correct
15 Correct 407 ms 1018344 KB Output is correct
16 Correct 408 ms 1018420 KB Output is correct
17 Correct 408 ms 1018496 KB Output is correct
18 Correct 427 ms 1018416 KB Output is correct
19 Correct 429 ms 1018472 KB Output is correct
20 Correct 411 ms 1018360 KB Output is correct
21 Correct 403 ms 1018464 KB Output is correct
22 Correct 391 ms 1018432 KB Output is correct
23 Correct 408 ms 1018408 KB Output is correct
24 Correct 391 ms 1018316 KB Output is correct
25 Correct 449 ms 1018336 KB Output is correct
26 Correct 388 ms 1018464 KB Output is correct
27 Correct 439 ms 1018424 KB Output is correct
28 Correct 405 ms 1018540 KB Output is correct
29 Correct 440 ms 1018396 KB Output is correct
30 Correct 415 ms 1018356 KB Output is correct
31 Correct 399 ms 1018448 KB Output is correct
32 Correct 402 ms 1018384 KB Output is correct
33 Correct 436 ms 1018412 KB Output is correct
34 Correct 402 ms 1018352 KB Output is correct
35 Correct 399 ms 1018388 KB Output is correct
36 Correct 385 ms 1018408 KB Output is correct
37 Correct 391 ms 1018376 KB Output is correct
38 Correct 388 ms 1018380 KB Output is correct
39 Correct 392 ms 1018360 KB Output is correct
40 Correct 449 ms 1018316 KB Output is correct
41 Correct 381 ms 1018384 KB Output is correct
42 Correct 408 ms 1018484 KB Output is correct
43 Correct 381 ms 1018424 KB Output is correct
44 Correct 402 ms 1018436 KB Output is correct
45 Correct 387 ms 1018408 KB Output is correct
46 Correct 405 ms 1018368 KB Output is correct
47 Correct 397 ms 1018432 KB Output is correct
48 Correct 385 ms 1018416 KB Output is correct
49 Correct 435 ms 1018416 KB Output is correct
50 Correct 424 ms 1018412 KB Output is correct
51 Correct 433 ms 1018404 KB Output is correct
52 Correct 407 ms 1018532 KB Output is correct
53 Correct 394 ms 1018556 KB Output is correct
54 Correct 396 ms 1018372 KB Output is correct
55 Correct 390 ms 1018464 KB Output is correct
56 Correct 408 ms 1018336 KB Output is correct
57 Correct 390 ms 1018364 KB Output is correct
58 Correct 462 ms 1018404 KB Output is correct
59 Correct 387 ms 1018528 KB Output is correct
60 Correct 382 ms 1018452 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1444 ms 1018456 KB Output is correct
2 Correct 1383 ms 1018440 KB Output is correct
3 Correct 1364 ms 1018440 KB Output is correct
4 Correct 1408 ms 1018436 KB Output is correct
5 Correct 1409 ms 1018440 KB Output is correct
6 Correct 1401 ms 1018440 KB Output is correct
7 Correct 1407 ms 1018440 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1018500 KB Output is correct
2 Correct 439 ms 1018316 KB Output is correct
3 Correct 398 ms 1018392 KB Output is correct
4 Correct 404 ms 1018316 KB Output is correct
5 Correct 400 ms 1018524 KB Output is correct
6 Correct 409 ms 1018344 KB Output is correct
7 Correct 445 ms 1018392 KB Output is correct
8 Correct 417 ms 1018444 KB Output is correct
9 Correct 404 ms 1018372 KB Output is correct
10 Correct 396 ms 1018444 KB Output is correct
11 Correct 444 ms 1018480 KB Output is correct
12 Correct 626 ms 1018348 KB Output is correct
13 Correct 625 ms 1018340 KB Output is correct
14 Correct 627 ms 1018524 KB Output is correct
15 Correct 1386 ms 1018440 KB Output is correct
16 Correct 1158 ms 1018540 KB Output is correct
17 Correct 714 ms 1018444 KB Output is correct
18 Correct 1460 ms 1018568 KB Output is correct
19 Correct 1049 ms 1018444 KB Output is correct
20 Correct 579 ms 1018616 KB Output is correct
21 Correct 401 ms 1018412 KB Output is correct
22 Correct 386 ms 1018424 KB Output is correct
23 Correct 407 ms 1018448 KB Output is correct
24 Correct 411 ms 1018424 KB Output is correct
25 Correct 436 ms 1018548 KB Output is correct
26 Correct 391 ms 1018312 KB Output is correct
27 Correct 438 ms 1018340 KB Output is correct
28 Correct 414 ms 1018320 KB Output is correct
29 Correct 452 ms 1018460 KB Output is correct
30 Correct 387 ms 1018348 KB Output is correct
31 Correct 448 ms 1018440 KB Output is correct
32 Correct 392 ms 1018404 KB Output is correct
33 Correct 443 ms 1018432 KB Output is correct
34 Correct 410 ms 1018316 KB Output is correct
35 Correct 407 ms 1018344 KB Output is correct
36 Correct 408 ms 1018420 KB Output is correct
37 Correct 408 ms 1018496 KB Output is correct
38 Correct 427 ms 1018416 KB Output is correct
39 Correct 429 ms 1018472 KB Output is correct
40 Correct 411 ms 1018360 KB Output is correct
41 Correct 403 ms 1018464 KB Output is correct
42 Correct 391 ms 1018432 KB Output is correct
43 Correct 408 ms 1018408 KB Output is correct
44 Correct 391 ms 1018316 KB Output is correct
45 Correct 449 ms 1018336 KB Output is correct
46 Correct 388 ms 1018464 KB Output is correct
47 Correct 439 ms 1018424 KB Output is correct
48 Correct 405 ms 1018540 KB Output is correct
49 Correct 440 ms 1018396 KB Output is correct
50 Correct 415 ms 1018356 KB Output is correct
51 Correct 399 ms 1018448 KB Output is correct
52 Correct 402 ms 1018384 KB Output is correct
53 Correct 436 ms 1018412 KB Output is correct
54 Correct 402 ms 1018352 KB Output is correct
55 Correct 399 ms 1018388 KB Output is correct
56 Correct 385 ms 1018408 KB Output is correct
57 Correct 391 ms 1018376 KB Output is correct
58 Correct 388 ms 1018380 KB Output is correct
59 Correct 392 ms 1018360 KB Output is correct
60 Correct 449 ms 1018316 KB Output is correct
61 Correct 381 ms 1018384 KB Output is correct
62 Correct 408 ms 1018484 KB Output is correct
63 Correct 381 ms 1018424 KB Output is correct
64 Correct 402 ms 1018436 KB Output is correct
65 Correct 387 ms 1018408 KB Output is correct
66 Correct 405 ms 1018368 KB Output is correct
67 Correct 397 ms 1018432 KB Output is correct
68 Correct 385 ms 1018416 KB Output is correct
69 Correct 435 ms 1018416 KB Output is correct
70 Correct 424 ms 1018412 KB Output is correct
71 Correct 433 ms 1018404 KB Output is correct
72 Correct 407 ms 1018532 KB Output is correct
73 Correct 394 ms 1018556 KB Output is correct
74 Correct 396 ms 1018372 KB Output is correct
75 Correct 390 ms 1018464 KB Output is correct
76 Correct 408 ms 1018336 KB Output is correct
77 Correct 390 ms 1018364 KB Output is correct
78 Correct 462 ms 1018404 KB Output is correct
79 Correct 387 ms 1018528 KB Output is correct
80 Correct 382 ms 1018452 KB Output is correct
81 Correct 1444 ms 1018456 KB Output is correct
82 Correct 1383 ms 1018440 KB Output is correct
83 Correct 1364 ms 1018440 KB Output is correct
84 Correct 1408 ms 1018436 KB Output is correct
85 Correct 1409 ms 1018440 KB Output is correct
86 Correct 1401 ms 1018440 KB Output is correct
87 Correct 1407 ms 1018440 KB Output is correct
88 Correct 443 ms 1018384 KB Output is correct
89 Correct 408 ms 1018316 KB Output is correct
90 Correct 573 ms 1018440 KB Output is correct
91 Correct 530 ms 1018440 KB Output is correct
92 Correct 1059 ms 1018520 KB Output is correct
93 Correct 1080 ms 1018320 KB Output is correct
94 Correct 1332 ms 1018444 KB Output is correct
95 Correct 1420 ms 1018436 KB Output is correct
96 Correct 1424 ms 1018552 KB Output is correct
97 Correct 1427 ms 1018548 KB Output is correct
98 Correct 1275 ms 1018440 KB Output is correct
99 Correct 1344 ms 1018440 KB Output is correct
100 Correct 1354 ms 1018440 KB Output is correct
101 Correct 1248 ms 1018440 KB Output is correct
102 Correct 1224 ms 1018340 KB Output is correct
103 Correct 1221 ms 1018316 KB Output is correct
104 Correct 1283 ms 1018624 KB Output is correct
105 Correct 1283 ms 1018388 KB Output is correct