Submission #865375

#	Time	Username	Problem	Language	Result	Execution time	Memory
865375		prairie2022	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	444 ms	600 KiB

Main

#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, 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<T; i++){
            if(dp[t]<big) 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);
            }
            if(dp[t]<ans) ans = min(ans, dp[t]+((ld)s[i+1])/(t+1));
        }
    }
    cout << fixed << setprecision(6) << ans << '\n';
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23