Submission #1276513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276513		Sofiatpc	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	117 ms	4420 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
const int MAXN = 505;
const double INF = 1e6;
pair<double, double> v[MAXN]; // b a
double dp[2][MAXN][MAXN];

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

    int n,k; cin>>n>>k;
    for(int i = 1; i <= n; i++){
        cin>>v[i].sc>>v[i].fi;
        if(v[i].fi == -1)v[i].fi = INF;
    }
    sort(v+1,v+1+n);

    for(int i = 1; i <= k; i++){
        dp[0][n+1][i] = INF;
        dp[1][k+1][i] = INF;
    }

    double ans = INF;
    for(int ini = 0; ini <= k; ini++){
        for(int i = n; i >= 1; i--)
            for(int y = 1; y <= k-ini; y++)
                dp[0][i][y] = min(dp[0][i+1][y], dp[0][i+1][y-1] + v[i].sc/double(ini+1));

        for(int i = k; i >= 1; i--){
            dp[1][i][0] = dp[0][i][k-i+1];
            for(int x = 1; x <= ini; x++){
                dp[1][i][x] = dp[1][i+1][x] + v[i].sc/double(ini+1);
                if(v[i].fi != -1)dp[1][i][x] = min(dp[1][i][x], dp[1][i+1][x-1] + v[i].fi/double(ini-x+1));
            }
        }
        ans = min(ans, dp[1][1][ini]);
    }
    cout<<fixed<<setprecision(15)<<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