Submission #1267692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267692		Sofiatpc	Let's Win the Election (JOI22_ho_t3)	C++20	56 / 100	2594 ms	2076 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;
    sort(v+1,v+1+n);

    double ans = INF;
    for(int ini = 0; ini <= k; ini++){
        for(int x = 0; x <= ini; x++)
            for(int y = 0; y <= k-x; y++)
                if(x != 0 || y != 0)dp[(n+1)%2][x][y] = INF;

        for(int i = n; i >= 1; i--)
            for(int x = 0; x <= ini; x++)
                for(int y = 0; y <= k-x; y++){
                    dp[i%2][x][y] = dp[(i+1)%2][x][y];
                    if(y > 0)
                        dp[i%2][x][y] = min( dp[i%2][x][y], dp[(i+1)%2][x][y-1] + (v[i].sc/(double(ini)+1)) );
                    if(x > 0 && v[i].fi != -1)
                        dp[i%2][x][y] = min( dp[i%2][x][y], dp[(i+1)%2][x-1][y] + (v[i].fi/(ini-x+1)) );
                }

        ans = min(ans, dp[1][ini][k-ini]);
    }
    cout<<fixed<<setprecision(15)<<ans<<"\n";

}

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