oj.uz

Submission #534374

# Submission time Handle Problem Language Result Execution time Memory
534374 2022-03-08T06:11:55 Z PixelCat Let's Win the Election (JOI22_ho_t3) C++14
11 / 100
 100 ms 4324 KB 
#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=INF;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 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 1 ms 332 KB Output is correct
2 Correct 0 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 0 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 0 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 0 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 98 ms 4320 KB Output is correct
2 Correct 84 ms 4300 KB Output is correct
3 Correct 77 ms 4324 KB Output is correct
4 Correct 100 ms 4320 KB Output is correct
5 Correct 78 ms 4320 KB Output is correct
6 Correct 67 ms 4280 KB Output is correct
7 Correct 70 ms 4244 KB Output is correct

Subtask #7
0 / 23.0

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