oj.uz

Submission #806060

# Submission time Handle Problem Language Result Execution time Memory
806060 2023-08-04T04:34:31 Z vjudge1 Let's Win the Election (JOI22_ho_t3) C++17
0 / 100
 2500 ms 8584 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 + 10];



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';
    ld res = INF;
    for(int _ = 0; _ < 1000; _++) {
        next_permutation(c + 1, c + n + 1);
        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';
        }
        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 1 ms 224 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 2554 ms 8584 KB Time limit exceeded
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 1 ms 224 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 2554 ms 8584 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2552 ms 8536 KB Time limit exceeded
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 1 ms 224 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 2554 ms 8584 KB Time limit exceeded
6 Halted 0 ms 0 KB -