Submission #831506

#	Time	Username	Problem	Language	Result	Execution time	Memory
831506		jasmin	Let's Win the Election (JOI22_ho_t3)	C++17	0 / 100	739 ms	1048576 KiB

Main

//JOI 2022 Final Round
#include<bits/stdc++.h>
using namespace std;
#define double long double

const int N=505;
double dp[N][N][N];

const double INF=1e9+7;

void init(){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            for(int k=0; k<N; k++){
                dp[i][j][k] = INF;
            }
        }
    }
}

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

    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];
    }

    vector<int> sorted(n);
    iota(sorted.begin(), sorted.end(), 0);
    sort(sorted.begin(), sorted.end(), [&](int i, int j){
        if(b[i]==-1) return false;
        if(b[j]==-1) return true;

        return b[i]<b[j];
    });

    cout.precision(300);

    init();
    dp[0][0][0]=(double)0;
    for(int i=0; i<n; i++){
        int ind=sorted[i];
        //cout << i << ": " << ind << "\n";

        for(int x=0; x<=i+1; x++){
            for(int y=0; y<=x; y++){

                dp[i+1][x][y] = dp[i][x][y];

                if(0<x){

                    dp[i+1][x][y] = min(dp[i+1][x][y], dp[i][x-1][y] + (double)a[ind]/(double)(y+1));
                }
                if(0<y && b[ind]!=-1){

                    dp[i+1][x][y] = min(dp[i+1][x][y], dp[i][x-1][y-1] + (double)b[ind]/(double)y);
                    //cout << dp[i][x-1][y-1] << "\n";
                }

                //cout << i << " " << x << " "  << y << ": " << dp[i+1][x][y] << "\n";

            }
        }
    }

    double ans=INF;
    for(int y=0; y<=n; y++){
        ans = min(ans, dp[n][k][y]);
    }
    cout << ans << "\n";
}

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