Submission #534375

#	Time	Username	Problem	Language	Result	Execution time	Memory
534375		PixelCat	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	75 ms	4344 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>;

const int MAXN=510;

double p[MAXN];
int a[MAXN];
int b[MAXN];
int mn[MAXN][MAXN];
double dp[MAXN][MAXN];

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // OAO
    int n,k; cin>>n>>k;
    {
        vector<pii> v(n);
        for(auto &i:v) cin>>i.F>>i.S;
        sort(all(v),[](const pii &pa,const pii &pb){
            if(pa.S==-1) return false;
            if(pb.S==-1) return true;
            return pa.S<pb.S;
        });
        For(i,0,n-1){
            a[i+1]=v[i].F;
            b[i+1]=v[i].S;
        }
    }
    For(i,1,n) p[i]=1.0/i;
    For(i,0,n){
        priority_queue<int> pq;
        int sum=0;
        Forr(j,n,1){
            sum+=a[j];
            pq.emplace(a[j]);
            if(sz(pq)>i){
                sum-=pq.top();
                pq.pop();
            }
            mn[i][j]=sum;
        }
    }
    // For(i,0,n) For(j,1,n) cout<<mn[i][j]<<" \n"[j==n];
    For(i,0,n) For(j,0,n) dp[i][j]=INF;
    dp[0][0]=0;
    double ans=mn[k][1];
    For(nc,0,k-1){
        For(i,1,n) For(j,0,min(i,nc)){
            dp[i][j]=dp[i-1][j]+a[i]*p[nc+1];
            if(b[i]!=-1 && j){
                dp[i][j]=min(dp[i][j],dp[i-1][j-1]+b[i]*p[j]);
            }
            if(j==nc){
                ans=min(ans,dp[i][j]+mn[k-i][i+1]*p[nc+1]);
            }
        }
    }
    cout<<fixed<<setprecision(15);
    cout<<ans<<"\n";
    return 0;
}

• 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