oj.uz

Submission #806033

# Submission time Handle Problem Language Result Execution time Memory
806033 2023-08-04T04:28:10 Z vjudge1 Let's Win the Election (JOI22_ho_t3) C++17
0 / 100
 2 ms 468 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 500;
const ld INF = 1e16;

int n, k;
pair<ld, ld> c[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> c[i].first >> c[i].second;
        if(c[i].second == -1) c[i].second = INF;
    }
    sort(c + 1, c + n + 1, [](pair<ld, ld> x, pair<ld, ld> y) {return x.second < y.second;});

    // for(int i = 1; i <= n; i++) 
    //     cout << c[i].first << ' ' << c[i].second << '\n';
    // cout << '\n';
    
    vector<vector<ld>> dp(n + 1, vector<ld>(n + 1, INF));
    dp[0][1] = 0;
    for(int i = 1; i <= n; i++) {
        vector<vector<ld>> newdp = dp;
        for(int k = 1; k <= i; k++) {
            for(int v = 1; v <= i + 1; v++) {
                newdp[k][v] = min(newdp[k][v], dp[k - 1][v] + c[i].first / v); 
                if(v > 1 && c[i].second != INF) 
                    newdp[k][v] = min(newdp[k][v], dp[k - 1][v - 1] + c[i].second / (v - 1)) ;
            }
        }
        dp = newdp;
        // for(int k = 1; k <= n; k++) {
        //     for(int v = 1; v <= n; v++) {
        //         cout <<setprecision(1) << fixed << dp[k][v] << ' ';
        //     }
        //     cout << '\n';
        // }
        // cout << '\n';
    }
    ld res = INF;
    for(int v = 1; v <= n; v++) {
        res = min(res, dp[k][v]);
    }
    cout << setprecision(9) << fixed << res ;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -