Submission #1156686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156686		fatman87878	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	896 ms	4424 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

#define db long double

constexpr int maxN=5e2+5;

int n,K;

db dp[maxN][maxN];

pair<db,db> val[maxN];

inline db DP(int G){
    for(int i = 0;i<=K;i++)for(int j = 0;j<=G;j++)dp[i][j] = 1e18;
    dp[0][0] = 0;
    for(int i = 0;i<n;i++){
        auto [b,a] = val[i];
        for(int j = min(K,i+1);j;j--){
            if(i+1==j){
                for(int k = G;k>=0;k--){
                    dp[j][k] = min(dp[j][k],dp[j-1][k] + a/(G+1));
                    if(k)dp[j][k] = min(dp[j][k],dp[j-1][k-1] + b/k);
                }
            }
            else {
                dp[j][G] = min(dp[j][G],dp[j-1][G] + a/(G+1));
            }
        }
    }
    return dp[K][G];
}

int main(){
    IOS
    cin>>n>>K;
    for(int i = 0;i<n;i++){
        cin>>val[i].second>>val[i].first;
        if(val[i].first==-1)val[i].first = 1e9;
    }
    sort(val,val+n);
    db ans = 1e18;
    for(int i = 0;i<K;i++)ans = min(ans,DP(i));
    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