oj.uz

Submission #534658

# Submission time Handle Problem Language Result Execution time Memory
534658 2022-03-08T13:09:16 Z Paul_Liao_1457 Let's Win the Election (JOI22_ho_t3) C++14
11 / 100
 306 ms 4344 KB 
// 還要更強
#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++;
            }
            //cout<<"suf["<<i<<"]["<<j<<"]="<<suf[i][j]<<endl;
        }
    }
    DB ans=1e8;
    for(DB tot=1;tot<=n;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;
        dp[1][1]=v[1].S;
        if(tot==1) ans=min(ans,dp[1][0]+suf[2][k-1]/tot);
        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) 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;
            //cout<<"dp="<<dp[i-1][j-1]+v[i].S/(DB)(j)<<endl;
            if(j+1==tot) ans=min(ans,dp[i][j]+suf[i+1][k-i]/tot);
            //cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<endl;
        }
    }
    cout<<fixed<<setprecision(5);
    cout<<ans<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 4296 KB Output is correct
2 Correct 288 ms 4296 KB Output is correct
3 Correct 282 ms 4332 KB Output is correct
4 Correct 274 ms 4292 KB Output is correct
5 Correct 280 ms 4344 KB Output is correct
6 Correct 269 ms 4292 KB Output is correct
7 Correct 269 ms 4256 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -