oj.uz

Submission #734568

# Submission time Handle Problem Language Result Execution time Memory
734568 2023-05-02T16:25:08 Z 1075508020060209tc Let's Win the Election (JOI22_ho_t3) C++14
11 / 100
 310 ms 4308 KB 
#include<bits/stdc++.h>
using namespace std;
//#define double long double
int n;int K;
int M;
pair<int,int>ar[200005];
double ans;

double dp[510][510];
int srtsf[510][510];
int srtps[510][510];
bool cmp(pair<int,int>i,pair<int,int>j){
if(i.second<j.second){return 1;}
if(i.second>j.second){return 0;}
if(i.first>j.first){return 1;}
return 0;
}

double solve(int m){

for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
        dp[i][j]=10000000;
    }
}

dp[1][0]=(double)ar[1].first/(double)(m+1);
dp[1][1]=ar[1].second;

for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        if(dp[i][j]>5000000){continue;}
        dp[i+1][j]=min(dp[i+1][j],dp[i][j]+(double)ar[i+1].first/(double)(m+1));
        dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+(double)ar[i+1].second/(double)(j+1));
    }
}
double ret=dp[K][m];
//cout<<fixed<<setprecision(6)<<ret<<"  ";
for(int i=K-1;i>=m;i--){
    ret=min(ret,dp[i][m]+(double)srtps[i+1][i+1+K-i-1]/(double)(m+1));
}
//cout<<fixed<<setprecision(6)<<ret<<endl;
return ret;
}


signed main(){
cin>>n>>K;
M=0;
for(int i=1;i<=n;i++){
    cin>>ar[i].first>>ar[i].second;
    if(ar[i].second==-1){
        ar[i].second=2000;
    }else{
        M++;
    }
}

sort(ar+1,ar+n+1,cmp);
/*
cout<<endl;
for(int i=1;i<=n;i++){
    cout<<ar[i].first<<" "<<ar[i].second<<endl;
}
cout<<endl;
*/
for(int i=1;i<=n;i++){

    for(int j=i;j<=n;j++){
        srtsf[i][j]=ar[j].first;
        //srtps[i][j]=srtsf[i][j]+srtps[i][j-1];
    }
    sort(srtsf[i]+i,srtsf[i]+n+1);
    for(int j=i;j<=n;j++){
        srtps[i][j]=srtsf[i][j]+srtps[i][j-1];
    }
}
/*
for(int i=1;i<=n;i++){

    for(int j=1;j<=n;j++){
        cout<<srtsf[i][j]<<" ";
    }cout<<endl;

}
*/



ans=5000000;
for(int i=0;i<=min(K,M);i++){
    ans=min(ans,solve(i));
}
cout<<fixed<<setprecision(6)<<ans<<endl;




/*


double l=0;double r=500000;
for(int ttt=0;ttt<90;ttt++){
    double mi=(l+r)/2;
    if(ok(mi)){
        l=mi;
    }else{
        r=mi;
    }
}

cout<<fixed<<setprecision(6)<<l<<endl;


*/

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 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 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 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 340 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 340 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 340 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 310 ms 4304 KB Output is correct
2 Correct 261 ms 4308 KB Output is correct
3 Correct 260 ms 4308 KB Output is correct
4 Correct 262 ms 4308 KB Output is correct
5 Correct 251 ms 4308 KB Output is correct
6 Correct 298 ms 4308 KB Output is correct
7 Correct 272 ms 4308 KB Output is correct

Subtask #7
0 / 23.0

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