oj.uz

Submission #572604

# Submission time Handle Problem Language Result Execution time Memory
572604 2022-06-04T19:06:16 Z JovanB Let's Win the Election (JOI22_ho_t3) C++17
21 / 100
 594 ms 6336 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 500;

ll dpm[N+5][N+5];
ld dp[N+5][N+5];
pair <int, int> a[N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, k;
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i].first >> a[i].second;
        if(a[i].second == -1) a[i].second = 1005;
    }
    sort(a+1, a+1+n, [](pair <int, int> x, pair <int, int> y){ if(x.second == y.second) return x.first < y.first; return x.second < y.second; });
    for(int j=1; j<=n; j++) dpm[n+1][j] = 1e18;
    for(int i=n; i>=1; i--){
        for(int j=1; j<=n; j++){
            dpm[i][j] = dpm[i+1][j];
            dpm[i][j] = min(dpm[i][j], dpm[i+1][j-1] + a[i].first);
        }
    }
    ld res = 1e18;
    for(int t=0; t<=k; t++){
        for(int j=1; j<=t; j++) dp[0][j] = 1e18;
        for(int i=1; i<=n; i++){
            for(int j=0; j<=t; j++){
                dp[i][j] = dp[i-1][j] + 1.0*a[i].first/(t + 1);
                if(a[i].second != 1005 && j) dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1.0*a[i].second/j);
            }
        }
        for(int i=1; i<=n; i++){
            if(i >= t && k >= i) res = min(res, dp[i][t] + 1.0*dpm[i+1][k-i]/(t + 1));
        }
    }
    cout << res << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 428 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 18 ms 5204 KB Output is correct
7 Correct 60 ms 6208 KB Output is correct
8 Correct 132 ms 6260 KB Output is correct
9 Correct 247 ms 6336 KB Output is correct
10 Correct 117 ms 6188 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 428 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 18 ms 5204 KB Output is correct
7 Correct 60 ms 6208 KB Output is correct
8 Correct 132 ms 6260 KB Output is correct
9 Correct 247 ms 6336 KB Output is correct
10 Correct 117 ms 6188 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 50 ms 5364 KB Output is correct
13 Correct 40 ms 5456 KB Output is correct
14 Correct 30 ms 5404 KB Output is correct
15 Correct 260 ms 6176 KB Output is correct
16 Correct 200 ms 6248 KB Output is correct
17 Correct 146 ms 6188 KB Output is correct
18 Correct 559 ms 6296 KB Output is correct
19 Correct 420 ms 6220 KB Output is correct
20 Correct 337 ms 6220 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 6256 KB Output is correct
2 Correct 569 ms 6256 KB Output is correct
3 Correct 594 ms 6260 KB Output is correct
4 Correct 548 ms 6272 KB Output is correct
5 Correct 580 ms 6256 KB Output is correct
6 Correct 514 ms 6256 KB Output is correct
7 Correct 579 ms 6204 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 428 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 18 ms 5204 KB Output is correct
7 Correct 60 ms 6208 KB Output is correct
8 Correct 132 ms 6260 KB Output is correct
9 Correct 247 ms 6336 KB Output is correct
10 Correct 117 ms 6188 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 50 ms 5364 KB Output is correct
13 Correct 40 ms 5456 KB Output is correct
14 Correct 30 ms 5404 KB Output is correct
15 Correct 260 ms 6176 KB Output is correct
16 Correct 200 ms 6248 KB Output is correct
17 Correct 146 ms 6188 KB Output is correct
18 Correct 559 ms 6296 KB Output is correct
19 Correct 420 ms 6220 KB Output is correct
20 Correct 337 ms 6220 KB Output is correct
21 Incorrect 1 ms 444 KB Output isn't correct
22 Halted 0 ms 0 KB -