Submission #831612

#	Time	Username	Problem	Language	Result	Execution time	Memory
831612		jasmin	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	410 ms	2604 KiB

Main

//JOI 2022 Final round
#include<bits/stdc++.h>
using namespace std;

const double INF=1e9+7;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cout.precision(100);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    vector<int> b(n);
    for(int i=0; i<n; i++){
        cin >> a[i] >> b[i];

        if(b[i]==-1) b[i]=INF;
    }

    vector<int> sorted(n);
    iota(sorted.begin(), sorted.end(), 0);
    sort(sorted.begin(), sorted.end(), [&](int i, int j){
        return b[i]<b[j];
    });

    double ans=INF;
    for(int c=0; c<=k; c++){

        vector<vector<double> > dp(n+1, vector<double> (k+1, INF));
        dp[0][0]=0;

        for(int i=0; i<n; i++){
            for(int j=0; j<= min(i+1, k); j++){
                int x=i+1-j;
                int ind=sorted[i];

                if(0<x && x<=c){

                    dp[i+1][j] = dp[i][j] + (double)b[ind]/(double)x;

                }
                else if(c<x){

                    dp[i+1][j] = dp[i][j];
                }

                if(0<j){

                    dp[i+1][j] = min(dp[i+1][j], dp[i][j-1] + (double)a[ind]/(double)(c+1));
                }

            }
        }

        ans = min(ans, dp[n][k-c]);
    }

    cout << ans << "\n";
}

• 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