oj.uz

Submission #916067

# Submission time Handle Problem Language Result Execution time Memory
916067 2024-01-25T08:32:35 Z yeediot Let's Win the Election (JOI22_ho_t3) C++14
21 / 100
 274 ms 5176 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define all(X) X.begin(),X.end()
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
bool cmp(pii a,pii b){
    if(a.S!=b.S)return a.S<b.S;
    return a.F<b.F;
}
const int inf=2e18;
signed main(){
    cout<<fixed<<setprecision(10);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    setio();
    int n,k;
    cin>>n>>k;
    vector<pii>vec;
    vec.pb({0,0});
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        vec.pb({a,b});
        if(b==-1){
            vec[i+1].S=inf;
        }
    }
    sort(all(vec),cmp);
    vector<vector<int>>suf(n+1,vector<int>(k+1));
    for(int i=1;i<=k;i++){
        multiset<int>st;
        int sum=0;
        for(int j=n;j>=1;j--){
            st.insert(vec[j].F);
            sum+=vec[j].F;
            if((int)(st.size())>i){
                sum-=*prev(st.end());
                st.erase(prev(st.end()));
            }
            if((int)(st.size())<i){
                suf[j][i]=inf;
            }
            else{
                suf[j][i]=sum;
            }
        }
    }
    double ans=inf;
    for(int p=0;p<=k;p++){
        vector<vector<double>>dp(n+1,vector<double>(p+1,inf));
        dp[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=p;j++){
                if(j)dp[i][j]=dp[i-1][j-1]+(double)vec[i].S/j;
                dp[i][j]=min(dp[i][j],dp[i-1][j]+(double)vec[i].F/(p+1));
                //cout<<i<<' '<<j<<' '<<dp[i][j]<<' '<<vec[i].F<<'\n';
                if(j==p){
                    if(i!=n)chmin(ans,dp[i][j]+(double)suf[i+1][k-i]/(p+1));
                    else chmin(ans,dp[i][j]);
                    //cout<<i<<' '<<j<<' '<<ans<<' '<<dp[i][j]<<'\n';
                }
            }
        }
        //cout<<ans<<'\n';
    }
    cout<<ans<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 904 KB Output is correct
6 Correct 18 ms 1676 KB Output is correct
7 Correct 64 ms 3132 KB Output is correct
8 Correct 139 ms 3832 KB Output is correct
9 Correct 238 ms 4700 KB Output is correct
10 Correct 119 ms 3428 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 904 KB Output is correct
6 Correct 18 ms 1676 KB Output is correct
7 Correct 64 ms 3132 KB Output is correct
8 Correct 139 ms 3832 KB Output is correct
9 Correct 238 ms 4700 KB Output is correct
10 Correct 119 ms 3428 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 27 ms 1992 KB Output is correct
13 Correct 25 ms 2024 KB Output is correct
14 Correct 25 ms 1912 KB Output is correct
15 Correct 125 ms 3436 KB Output is correct
16 Correct 120 ms 3640 KB Output is correct
17 Correct 128 ms 3576 KB Output is correct
18 Correct 249 ms 4760 KB Output is correct
19 Correct 258 ms 4992 KB Output is correct
20 Correct 274 ms 4768 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 348 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 348 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 245 ms 5176 KB Output is correct
2 Correct 239 ms 4824 KB Output is correct
3 Correct 239 ms 4752 KB Output is correct
4 Correct 242 ms 4760 KB Output is correct
5 Correct 244 ms 4716 KB Output is correct
6 Correct 244 ms 4932 KB Output is correct
7 Correct 243 ms 4712 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 904 KB Output is correct
6 Correct 18 ms 1676 KB Output is correct
7 Correct 64 ms 3132 KB Output is correct
8 Correct 139 ms 3832 KB Output is correct
9 Correct 238 ms 4700 KB Output is correct
10 Correct 119 ms 3428 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 27 ms 1992 KB Output is correct
13 Correct 25 ms 2024 KB Output is correct
14 Correct 25 ms 1912 KB Output is correct
15 Correct 125 ms 3436 KB Output is correct
16 Correct 120 ms 3640 KB Output is correct
17 Correct 128 ms 3576 KB Output is correct
18 Correct 249 ms 4760 KB Output is correct
19 Correct 258 ms 4992 KB Output is correct
20 Correct 274 ms 4768 KB Output is correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -