oj.uz

Submission #865318

# Submission time Handle Problem Language Result Execution time Memory
865318 2023-10-24T07:23:18 Z prairie2022 Let's Win the Election (JOI22_ho_t3) C++17
5 / 100
 400 ms 600 KB 
#include<bits/stdc++.h>
typedef long double ld;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
using namespace std;

#define pii pair<int, int>
#define F first 
#define S second

int main(){
    fastio
    const int big = 5e5+1;
    int n, k, T = 0;
    cin >> n >> k;
    vector<pii> ba(n);
    for(int i=0; i<n; i++){
        cin >> ba[i].S >> ba[i].F;
        if(ba[i].F==-1){
            ba[i].F = big;
            T++;
        }
    }
    sort(ba.begin(), ba.end());
    //s[i] = min sum of k-i elements from [i, n)
    T = min(k-1, n-T);
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<int> s(T+1);
    for(int i=T; i<n; i++) pq.push(ba[i].S);
    s[T] = 0;
    for(int i=0; i<k-T; i++){
        s[T] += pq.top();
        pq.pop();
    }
    for(int i=T-1; i>-1; i--){
        pq.push(ba[i].S);
        s[i] = s[i+1]+pq.top();
        pq.pop();
    }
    //dp by #collaborator
    ld ans = s[0];
    for(int t=1; t<=T; t++){
        vector<ld> dp(t+1, big);
        dp[0] = 0;
        for(int i=0; i<k; i++){
            if(ba[i].F==big) break;
            if(dp[t]!=big){
                ans = min(ans, dp[t]+((ld)s[i])/(t+1));
                dp[t] += ((ld)ba[i].S)/(t+1);
            }
            for(int j=t-1; j>-1; j--){
                if(dp[j]==big) continue;
                dp[j+1] = min(dp[j+1], dp[j]+((ld)ba[i].F)/(j+1));
                dp[j] += ((ld)ba[i].S)/(t+1);
            }
        }
    }
    cout << fixed << setprecision(6) << ans << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 12 ms 504 KB Output is correct
13 Correct 11 ms 348 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 144 ms 488 KB Output is correct
16 Correct 79 ms 348 KB Output is correct
17 Incorrect 3 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 476 KB Output is correct
2 Correct 390 ms 600 KB Output is correct
3 Correct 386 ms 476 KB Output is correct
4 Incorrect 381 ms 476 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 12 ms 504 KB Output is correct
13 Correct 11 ms 348 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 144 ms 488 KB Output is correct
16 Correct 79 ms 348 KB Output is correct
17 Incorrect 3 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -