Submission #534664

#	Time	Username	Problem	Language	Result	Execution time	Memory
534664		Paul_Liao_1457	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	374 ms	4412 KiB

Main

// 還要更強
#include<iostream>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<math.h>
#include<cstring>
#include<stack>
#include<string.h>
#include<random>
#include<algorithm>
#include<vector>
 
#define ll long long
#define DB double
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(ll i=a;i>=b;i--)
#define F first
#define S second
#define INF (int)1e9+5
#define MOD (ll)(998244353)
#define pb push_back
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
 
using namespace std;
 
template<class T> using PQ=priority_queue<T,vector<T>,greater<T> >;
mt19937 rng(random_device{}());

int n,k;
vector<pair<DB,DB> > v;

bool cmp(pair<DB,DB> a,pair<DB,DB> b){
    return a.S<b.S;
}

DB dp[505][505];
DB suf[505][505];
multiset<int> mst;

signed main(){
    AC;
    cin>>n>>k;
    v.pb({0,0});
    FOR(i,0,n){
        int a,b; cin>>a>>b; if(b==-1) b=2000;
        v.pb({a,b});
    }
    sort(v.begin()+1,v.end(),cmp);
    
    REP(i,n,1){
        mst.insert(v[i].F);
        FOR(j,1,n-i+2){
            int cnt=j;
            auto it=mst.begin();
            while(cnt--){
                suf[i][j]+=*it; it++;
            }
        }
    }
    DB ans=1e9;
    for(DB tot=1;tot<=n+1;tot++){
        FOR(i,1,n+1)FOR(j,0,n+1) dp[i][j]=1e9;
        //cout<<"tot="<<tot<<endl;
        dp[1][0]=v[1].F/tot;
        if(v[1].S!=2000) dp[1][1]=v[1].S;
        if(tot==1){
            ans=min(ans,dp[1][0]+suf[2][k-1]/tot);
            ans=min(ans,suf[1][k]);
        }
        else if(tot==2) ans=min(ans,dp[1][1]+suf[2][k-1]/tot);
        //cout<<"why="<<dp[1][1]+suf[2][k-1]/tot<<endl;
        FOR(i,2,n+1)FOR(j,0,min(i,(int)tot)+1){
            if(j&&v[i].S!=2000) dp[i][j]=min(dp[i-1][j]+v[i].F/tot,dp[i-1][j-1]+v[i].S/(DB)(j));
            else dp[i][j]=dp[i-1][j]+v[i].F/tot;
            if(j+1==tot) ans=min(ans,dp[i][j]+suf[i+1][k-i]/tot);
        }
    }
    cout<<fixed<<setprecision(5);
    cout<<ans<<endl;
}

• 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