oj.uz

Submission #785050

# Submission time Handle Problem Language Result Execution time Memory
785050 2023-07-17T02:18:31 Z gun_gan Let's Win the Election (JOI22_ho_t3) C++17
5 / 100
 561 ms 1008556 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) {
            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 354 ms 1008448 KB Output is correct
2 Correct 376 ms 1008316 KB Output is correct
3 Correct 355 ms 1008332 KB Output is correct
4 Correct 349 ms 1008400 KB Output is correct
5 Correct 459 ms 1008528 KB Output is correct
6 Correct 448 ms 1008388 KB Output is correct
7 Correct 462 ms 1008556 KB Output is correct
8 Correct 457 ms 1008384 KB Output is correct
9 Correct 476 ms 1008384 KB Output is correct
10 Correct 470 ms 1008476 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 1008448 KB Output is correct
2 Correct 376 ms 1008316 KB Output is correct
3 Correct 355 ms 1008332 KB Output is correct
4 Correct 349 ms 1008400 KB Output is correct
5 Correct 459 ms 1008528 KB Output is correct
6 Correct 448 ms 1008388 KB Output is correct
7 Correct 462 ms 1008556 KB Output is correct
8 Correct 457 ms 1008384 KB Output is correct
9 Correct 476 ms 1008384 KB Output is correct
10 Correct 470 ms 1008476 KB Output is correct
11 Correct 363 ms 1008384 KB Output is correct
12 Incorrect 561 ms 1008432 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 1008332 KB Output is correct
2 Correct 381 ms 1008400 KB Output is correct
3 Incorrect 354 ms 1008364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 1008332 KB Output is correct
2 Correct 381 ms 1008400 KB Output is correct
3 Incorrect 354 ms 1008364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 1008332 KB Output is correct
2 Correct 381 ms 1008400 KB Output is correct
3 Incorrect 354 ms 1008364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 1008448 KB Output is correct
2 Correct 376 ms 1008316 KB Output is correct
3 Correct 355 ms 1008332 KB Output is correct
4 Correct 349 ms 1008400 KB Output is correct
5 Correct 459 ms 1008528 KB Output is correct
6 Correct 448 ms 1008388 KB Output is correct
7 Correct 462 ms 1008556 KB Output is correct
8 Correct 457 ms 1008384 KB Output is correct
9 Correct 476 ms 1008384 KB Output is correct
10 Correct 470 ms 1008476 KB Output is correct
11 Correct 363 ms 1008384 KB Output is correct
12 Incorrect 561 ms 1008432 KB Output isn't correct
13 Halted 0 ms 0 KB -