oj.uz

Submission #794840

# Submission time Handle Problem Language Result Execution time Memory
794840 2023-07-27T01:01:13 Z gun_gan Let's Win the Election (JOI22_ho_t3) C++17
16 / 100
 1586 ms 499148 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;

double f(int x) {
      for(int i = 0; i <= N; i++)
            for(int j = 0; j <= min(i, K); j++)
                  for(int k = 0; k <= min(i, x); k++)
                        dp[i][j][k] = 1e9;
       
      dp[0][0][0] = 0;
      for(int i = 0; i < N; i++) {
            for(int j = 0; j <= min(i, K); j++) { // votes
                  for(int k = 0; k <= min(i, x); 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 / (x + 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));
                  }
            }
      }

      return dp[N][K][x];
}
 
int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      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());

      double ans = 1e9;

      int mid = min(K, tot) / 2;
      for(int i = max(0, mid - 5); i <= min(min(K, tot), mid + 5); i++) ans = min(ans, f(i));


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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 37 ms 99812 KB Output is correct
6 Correct 72 ms 221644 KB Output is correct
7 Correct 117 ms 375588 KB Output is correct
8 Correct 140 ms 467752 KB Output is correct
9 Correct 151 ms 498328 KB Output is correct
10 Correct 140 ms 454404 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 37 ms 99812 KB Output is correct
6 Correct 72 ms 221644 KB Output is correct
7 Correct 117 ms 375588 KB Output is correct
8 Correct 140 ms 467752 KB Output is correct
9 Correct 151 ms 498328 KB Output is correct
10 Correct 140 ms 454404 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Incorrect 469 ms 257752 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 1 ms 1236 KB Output is correct
21 Correct 1 ms 1236 KB Output is correct
22 Correct 1 ms 1236 KB Output is correct
23 Correct 1 ms 1236 KB Output is correct
24 Correct 1 ms 1236 KB Output is correct
25 Correct 1 ms 1236 KB Output is correct
26 Correct 1 ms 1236 KB Output is correct
27 Incorrect 1 ms 1236 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 1 ms 1236 KB Output is correct
21 Correct 1 ms 1236 KB Output is correct
22 Correct 1 ms 1236 KB Output is correct
23 Correct 1 ms 1236 KB Output is correct
24 Correct 1 ms 1236 KB Output is correct
25 Correct 1 ms 1236 KB Output is correct
26 Correct 1 ms 1236 KB Output is correct
27 Incorrect 1 ms 1236 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 37 ms 99812 KB Output is correct
6 Correct 72 ms 221644 KB Output is correct
7 Correct 117 ms 375588 KB Output is correct
8 Correct 140 ms 467752 KB Output is correct
9 Correct 151 ms 498328 KB Output is correct
10 Correct 140 ms 454404 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Incorrect 469 ms 257752 KB Output isn't correct
13 Halted 0 ms 0 KB -