oj.uz

Submission #785042

# Submission time Handle Problem Language Result Execution time Memory
785042 2023-07-17T01:00:40 Z gun_gan Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 577 ms 1008644 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 505;

int N, K;
int a[MX], b[MX];
double dp[MX][MX][MX];

vector<pair<int, int>> v;

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      for(int i = 0; i < MX; i++)
            for(int j = 0; j < MX; j++)
                  for(int k = 0; k < MX; k++)
                        dp[i][j][k] = 1e9;

      cin >> N >> K;

      int tot = 0;
      for(int i = 1; i <= N; i++) {
            cin >> a[i] >> b[i];
            if(b[i] != -1) tot++;
            else b[i] = 1e9;
            v.push_back({b[i], a[i]});
      }

      sort(v.begin(), v.end());

      dp[0][0][0] = 0;
      for(int i = 0; i <= N; i++) {
            for(int j = 0; j <= N; j++) { // votes
                  for(int k = 0; k <= N; k++) { // num of collaborator

                        if(dp[i][j][k] == 1e9) continue;

                        // skip
                        dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
                        // ambil vote
                        dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] + (double) v[i].second / (k + 1));
                        
                        // ambil collaborator
                        if(v[i].first != 1e9) 
                              dp[i + 1][j + 1][k + 1] = min(dp[i + 1][j + 1][k + 1], dp[i][j][k] + (double) v[i].first / (k + 1));
                  }
            }
      }

      double ans = 1e9;
      for(int k = 0; k <= N; k++) {
            ans = min(ans, dp[N][K][k]);
      }

      cout << fixed << setprecision(15) << ans << '\n';

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 1008332 KB Output is correct
2 Correct 348 ms 1008432 KB Output is correct
3 Correct 347 ms 1008404 KB Output is correct
4 Correct 346 ms 1008376 KB Output is correct
5 Correct 451 ms 1008332 KB Output is correct
6 Correct 513 ms 1008436 KB Output is correct
7 Correct 452 ms 1008356 KB Output is correct
8 Correct 488 ms 1008360 KB Output is correct
9 Correct 449 ms 1008436 KB Output is correct
10 Correct 458 ms 1008400 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 1008332 KB Output is correct
2 Correct 348 ms 1008432 KB Output is correct
3 Correct 347 ms 1008404 KB Output is correct
4 Correct 346 ms 1008376 KB Output is correct
5 Correct 451 ms 1008332 KB Output is correct
6 Correct 513 ms 1008436 KB Output is correct
7 Correct 452 ms 1008356 KB Output is correct
8 Correct 488 ms 1008360 KB Output is correct
9 Correct 449 ms 1008436 KB Output is correct
10 Correct 458 ms 1008400 KB Output is correct
11 Correct 352 ms 1008332 KB Output is correct
12 Correct 518 ms 1008408 KB Output is correct
13 Correct 502 ms 1008644 KB Output is correct
14 Correct 489 ms 1008432 KB Output is correct
15 Correct 518 ms 1008432 KB Output is correct
16 Correct 503 ms 1008500 KB Output is correct
17 Correct 476 ms 1008352 KB Output is correct
18 Correct 518 ms 1008480 KB Output is correct
19 Correct 501 ms 1008332 KB Output is correct
20 Correct 484 ms 1008372 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 1008404 KB Output is correct
2 Correct 359 ms 1008352 KB Output is correct
3 Correct 405 ms 1008412 KB Output is correct
4 Correct 350 ms 1008376 KB Output is correct
5 Correct 347 ms 1008364 KB Output is correct
6 Correct 353 ms 1008320 KB Output is correct
7 Correct 357 ms 1008360 KB Output is correct
8 Correct 347 ms 1008332 KB Output is correct
9 Incorrect 350 ms 1008312 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 1008404 KB Output is correct
2 Correct 359 ms 1008352 KB Output is correct
3 Correct 405 ms 1008412 KB Output is correct
4 Correct 350 ms 1008376 KB Output is correct
5 Correct 347 ms 1008364 KB Output is correct
6 Correct 353 ms 1008320 KB Output is correct
7 Correct 357 ms 1008360 KB Output is correct
8 Correct 347 ms 1008332 KB Output is correct
9 Incorrect 350 ms 1008312 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 1008404 KB Output is correct
2 Correct 359 ms 1008352 KB Output is correct
3 Correct 405 ms 1008412 KB Output is correct
4 Correct 350 ms 1008376 KB Output is correct
5 Correct 347 ms 1008364 KB Output is correct
6 Correct 353 ms 1008320 KB Output is correct
7 Correct 357 ms 1008360 KB Output is correct
8 Correct 347 ms 1008332 KB Output is correct
9 Incorrect 350 ms 1008312 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 577 ms 1008432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 1008332 KB Output is correct
2 Correct 348 ms 1008432 KB Output is correct
3 Correct 347 ms 1008404 KB Output is correct
4 Correct 346 ms 1008376 KB Output is correct
5 Correct 451 ms 1008332 KB Output is correct
6 Correct 513 ms 1008436 KB Output is correct
7 Correct 452 ms 1008356 KB Output is correct
8 Correct 488 ms 1008360 KB Output is correct
9 Correct 449 ms 1008436 KB Output is correct
10 Correct 458 ms 1008400 KB Output is correct
11 Correct 352 ms 1008332 KB Output is correct
12 Correct 518 ms 1008408 KB Output is correct
13 Correct 502 ms 1008644 KB Output is correct
14 Correct 489 ms 1008432 KB Output is correct
15 Correct 518 ms 1008432 KB Output is correct
16 Correct 503 ms 1008500 KB Output is correct
17 Correct 476 ms 1008352 KB Output is correct
18 Correct 518 ms 1008480 KB Output is correct
19 Correct 501 ms 1008332 KB Output is correct
20 Correct 484 ms 1008372 KB Output is correct
21 Correct 364 ms 1008404 KB Output is correct
22 Correct 359 ms 1008352 KB Output is correct
23 Correct 405 ms 1008412 KB Output is correct
24 Correct 350 ms 1008376 KB Output is correct
25 Correct 347 ms 1008364 KB Output is correct
26 Correct 353 ms 1008320 KB Output is correct
27 Correct 357 ms 1008360 KB Output is correct
28 Correct 347 ms 1008332 KB Output is correct
29 Incorrect 350 ms 1008312 KB Output isn't correct
30 Halted 0 ms 0 KB -