oj.uz

답안 #794839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794839 2023-07-27T01:00:35 Z gun_gan Let's Win the Election (JOI22_ho_t3) C++17
16 / 100
 793 ms 499156 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 - 2); i <= min(min(K, tot), mid + 2); i++) ans = min(ans, f(i));


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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 35 ms 99804 KB Output is correct
6 Correct 71 ms 221716 KB Output is correct
7 Correct 115 ms 375608 KB Output is correct
8 Correct 139 ms 467728 KB Output is correct
9 Correct 149 ms 498416 KB Output is correct
10 Correct 142 ms 454264 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 35 ms 99804 KB Output is correct
6 Correct 71 ms 221716 KB Output is correct
7 Correct 115 ms 375608 KB Output is correct
8 Correct 139 ms 467728 KB Output is correct
9 Correct 149 ms 498416 KB Output is correct
10 Correct 142 ms 454264 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Incorrect 235 ms 257740 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 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 1 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 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 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 1 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 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 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 1116 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Incorrect 1 ms 1236 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 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 1 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 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 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 1116 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Incorrect 1 ms 1236 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 793 ms 499156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 35 ms 99804 KB Output is correct
6 Correct 71 ms 221716 KB Output is correct
7 Correct 115 ms 375608 KB Output is correct
8 Correct 139 ms 467728 KB Output is correct
9 Correct 149 ms 498416 KB Output is correct
10 Correct 142 ms 454264 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Incorrect 235 ms 257740 KB Output isn't correct
13 Halted 0 ms 0 KB -