Submission #1169400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169400		Newtonabc	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	613 ms	4472 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=510;
double a[N],b[N];
vector<pair<double,double>> v;
double dp[N][N],dpb[N][N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,vt,t=0;
    cin>>n >>vt;
    for(int i=1;i<=n;i++){
        cin>>a[i] >>b[i];
        if(b[i]==-1) b[i]=1e9;
        else t++;
        v.push_back({b[i],a[i]});
    }
    sort(v.begin(),v.end());
    double ans=INT_MAX;
    for(int g=0;g<=min(t,vt);g++){
        for(int i=0;i<=n;i++) for(int k=0;k<=vt;k++) dp[i][k]=INT_MAX;
        //think that dp[i][j]=dp[i][i][j] and dpb[i][j]=dp[i][j][g]
        dp[0][0]=0;
        for(int i=0;i<=n;i++) for(int j=0;j<=vt;j++) dpb[i][j]=INT_MAX;
        if(g==0) for(int i=0;i<=n;i++) dpb[i][0]=0;
        for(int i=1;i<=n;i++){
            for(int k=0;k<g;k++){
                if(k-1>=0) dp[i][k]=min(dp[i][k],dp[i-1][k-1]+v[i-1].first/(double)k);
                dp[i][k]=min(dp[i][k],dp[i-1][k]+v[i-1].second/(double)(g+1));
            }
            for(int j=1;j<=vt;j++){
                dpb[i][j]=min(dpb[i][j],dpb[i-1][j]);
                if(g-1>=0 && i==j) dpb[i][j]=min(dpb[i][j],dp[i-1][g-1]+v[i-1].first/(double)g);
                dpb[i][j]=min(dpb[i][j],dpb[i-1][j-1]+v[i-1].second/(double)(g+1));
            }
        }
        ans=min(ans,dpb[n][vt]);
    }
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=vt;j++){
    //         if(dp[i][j]==INT_MAX) cout<<"- ";
    //         else cout<<dp[i][j] <<" ";
    //     }
    //     cout<<"\n";
    // }  
    // cout<<"\n";
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=vt;j++){
    //         if(dpb[i][j]==INT_MAX) cout<<"- ";
    //         else cout<<dpb[i][j] <<" ";
    //     }
    //     cout<<"\n";
    // }  
    cout<<fixed <<setprecision(9) <<ans;

    
}

• 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