oj.uz

Submission #785052

# Submission time Handle Problem Language Result Execution time Memory
785052 2023-07-17T02:26:51 Z gun_gan Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 556 ms 1008536 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;
 
      for(int i = 1; i <= N; i++) {
            cin >> a[i] >> b[i];
            v.push_back({b[i], a[i]});
      }
 
      sort(v.begin(), v.end(), [&](auto x, auto y) {
            if(x.first == -1 && y.first == -1) return x.second < y.second;
            if(x.first == -1) return false;
            if(y.first == -1) return true;

            if(x.first - x.second == y.first - y.second) return x.first < y.first;

            return x.first - x.second < y.first - y.second;
      });
 
      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 != -1) 
                              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 406 ms 1008400 KB Output is correct
2 Correct 370 ms 1008404 KB Output is correct
3 Correct 371 ms 1008320 KB Output is correct
4 Correct 359 ms 1008392 KB Output is correct
5 Correct 491 ms 1008368 KB Output is correct
6 Correct 493 ms 1008396 KB Output is correct
7 Correct 482 ms 1008408 KB Output is correct
8 Correct 492 ms 1008432 KB Output is correct
9 Correct 491 ms 1008440 KB Output is correct
10 Correct 487 ms 1008432 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 1008400 KB Output is correct
2 Correct 370 ms 1008404 KB Output is correct
3 Correct 371 ms 1008320 KB Output is correct
4 Correct 359 ms 1008392 KB Output is correct
5 Correct 491 ms 1008368 KB Output is correct
6 Correct 493 ms 1008396 KB Output is correct
7 Correct 482 ms 1008408 KB Output is correct
8 Correct 492 ms 1008432 KB Output is correct
9 Correct 491 ms 1008440 KB Output is correct
10 Correct 487 ms 1008432 KB Output is correct
11 Correct 353 ms 1008420 KB Output is correct
12 Correct 539 ms 1008432 KB Output is correct
13 Correct 541 ms 1008436 KB Output is correct
14 Correct 509 ms 1008352 KB Output is correct
15 Correct 538 ms 1008424 KB Output is correct
16 Correct 523 ms 1008432 KB Output is correct
17 Correct 524 ms 1008352 KB Output is correct
18 Correct 542 ms 1008332 KB Output is correct
19 Correct 528 ms 1008460 KB Output is correct
20 Correct 517 ms 1008440 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 1008332 KB Output is correct
2 Correct 349 ms 1008492 KB Output is correct
3 Correct 350 ms 1008368 KB Output is correct
4 Correct 356 ms 1008536 KB Output is correct
5 Correct 375 ms 1008332 KB Output is correct
6 Correct 402 ms 1008356 KB Output is correct
7 Incorrect 359 ms 1008304 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 1008332 KB Output is correct
2 Correct 349 ms 1008492 KB Output is correct
3 Correct 350 ms 1008368 KB Output is correct
4 Correct 356 ms 1008536 KB Output is correct
5 Correct 375 ms 1008332 KB Output is correct
6 Correct 402 ms 1008356 KB Output is correct
7 Incorrect 359 ms 1008304 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 1008332 KB Output is correct
2 Correct 349 ms 1008492 KB Output is correct
3 Correct 350 ms 1008368 KB Output is correct
4 Correct 356 ms 1008536 KB Output is correct
5 Correct 375 ms 1008332 KB Output is correct
6 Correct 402 ms 1008356 KB Output is correct
7 Incorrect 359 ms 1008304 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 1008400 KB Output is correct
2 Correct 370 ms 1008404 KB Output is correct
3 Correct 371 ms 1008320 KB Output is correct
4 Correct 359 ms 1008392 KB Output is correct
5 Correct 491 ms 1008368 KB Output is correct
6 Correct 493 ms 1008396 KB Output is correct
7 Correct 482 ms 1008408 KB Output is correct
8 Correct 492 ms 1008432 KB Output is correct
9 Correct 491 ms 1008440 KB Output is correct
10 Correct 487 ms 1008432 KB Output is correct
11 Correct 353 ms 1008420 KB Output is correct
12 Correct 539 ms 1008432 KB Output is correct
13 Correct 541 ms 1008436 KB Output is correct
14 Correct 509 ms 1008352 KB Output is correct
15 Correct 538 ms 1008424 KB Output is correct
16 Correct 523 ms 1008432 KB Output is correct
17 Correct 524 ms 1008352 KB Output is correct
18 Correct 542 ms 1008332 KB Output is correct
19 Correct 528 ms 1008460 KB Output is correct
20 Correct 517 ms 1008440 KB Output is correct
21 Correct 350 ms 1008332 KB Output is correct
22 Correct 349 ms 1008492 KB Output is correct
23 Correct 350 ms 1008368 KB Output is correct
24 Correct 356 ms 1008536 KB Output is correct
25 Correct 375 ms 1008332 KB Output is correct
26 Correct 402 ms 1008356 KB Output is correct
27 Incorrect 359 ms 1008304 KB Output isn't correct
28 Halted 0 ms 0 KB -