Submission #534274

#	Time	Username	Problem	Language	Result	Execution time	Memory
534274		PixelCat	Let's Win the Election (JOI22_ho_t3)	C++14	72 / 100	2628 ms	1004488 KiB

Main

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define INF (LL)(9e18)
#define int LL
using namespace std;
using LL=long long;
using pii=pair<int,int>;

template<typename T>
void chmin(T &_a,const T &_b){
    if(_a>_b) _a=_b;
}

const int MAXN=510;

double p[MAXN];
pii a[MAXN];
double dp[MAXN][MAXN][MAXN];

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // OAO
    int n,K; cin>>n>>K;
    bool oao=true;
    For(i,1,n){
        cin>>a[i].F>>a[i].S;
        if(a[i].S!=-1) oao=false;
    }
    if(oao){
        sort(a+1,a+n+1,[](pii &pa,pii &pb){
            return pa.F<pb.F;
        });
        int tot=0;
        For(i,1,K) tot+=a[i].F;
        cout<<tot<<"\n";
        return 0;
    }
    sort(a+1,a+n+1,[](pii &pa,pii &pb){
        return pa.S<pb.S;
    });
    // For(i,1,n) cerr<<a[i].F<<" "<<a[i].S<<"\n";
    p[0]=1;
    For(i,1,n) p[i]=1.0/(i+1);
    For(i,0,n) For(j,0,n) For(k,0,n) dp[i][j][k]=INF;
    dp[0][0][0]=0;
    if(n==K){
        double ans=INF;
        For(nc,0,n){
            For(i,1,n) For(j,0,min(i,nc)){
                dp[0][i][j]=dp[0][i-1][j]+a[i].F*p[nc];
                if(a[i].S!=-1 && j){
                    chmin(dp[0][i][j],dp[0][i-1][j-1]+a[i].S*p[j-1]);
                }
            }
            chmin(ans,dp[0][n][nc]);
        }
        cout<<fixed<<setprecision(15);
        cout<<ans<<"\n";
        return 0;
    }
    double ans=INF;
    For(nc,0,K){
        For(i,1,n) For(j,0,min(i,K)) For(k,0,min(j,nc)){
            dp[i][j][k]=dp[i-1][j][k];
            if(j){
                chmin(dp[i][j][k],dp[i-1][j-1][k]+a[i].F*p[nc]);
            }
            if(a[i].S!=-1 && k){
                chmin(dp[i][j][k],dp[i-1][j-1][k-1]+a[i].S*p[k-1]);
            }
        }
        // if(nc==3){
        //     For(i,1,n) For(j,0,K) For(k,0,nc){
        //         cerr<<dp[i][j][k]<<"\t\n"[k==nc];
        //         if(j==K && k==nc) cerr<<"\n";
        //     }
        // }
        // cerr<<nc<<" "<<dp[n][K][nc]<<"\n";
        chmin(ans,dp[n][K][nc]);
    }
    cout<<fixed<<setprecision(15);
    cout<<ans<<"\n";
    return 0;
}

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