oj.uz

Submission #734566

# Submission time Handle Problem Language Result Execution time Memory
734566 2023-05-02T16:16:14 Z 1075508020060209tc Let's Win the Election (JOI22_ho_t3) C++14
21 / 100
 1372 ms 6436 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]=1000000;
    }
}

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]>500000){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++;
    }
}
//cout<<endl;
sort(ar+1,ar+n+1,cmp);
/*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=500000;
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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 6228 KB Output is correct
6 Correct 6 ms 6228 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct
8 Correct 7 ms 6228 KB Output is correct
9 Correct 6 ms 6332 KB Output is correct
10 Correct 6 ms 6252 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 6228 KB Output is correct
6 Correct 6 ms 6228 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct
8 Correct 7 ms 6228 KB Output is correct
9 Correct 6 ms 6332 KB Output is correct
10 Correct 6 ms 6252 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 296 ms 6300 KB Output is correct
13 Correct 291 ms 6296 KB Output is correct
14 Correct 172 ms 6228 KB Output is correct
15 Correct 858 ms 6300 KB Output is correct
16 Correct 676 ms 6304 KB Output is correct
17 Correct 180 ms 6304 KB Output is correct
18 Correct 1324 ms 6308 KB Output is correct
19 Correct 693 ms 6300 KB Output is correct
20 Correct 161 ms 6304 KB Output is correct

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 1299 ms 6300 KB Output is correct
2 Correct 1292 ms 6304 KB Output is correct
3 Correct 1267 ms 6428 KB Output is correct
4 Correct 1262 ms 6436 KB Output is correct
5 Correct 1313 ms 6300 KB Output is correct
6 Correct 1372 ms 6308 KB Output is correct
7 Correct 1255 ms 6304 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 6228 KB Output is correct
6 Correct 6 ms 6228 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct
8 Correct 7 ms 6228 KB Output is correct
9 Correct 6 ms 6332 KB Output is correct
10 Correct 6 ms 6252 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 296 ms 6300 KB Output is correct
13 Correct 291 ms 6296 KB Output is correct
14 Correct 172 ms 6228 KB Output is correct
15 Correct 858 ms 6300 KB Output is correct
16 Correct 676 ms 6304 KB Output is correct
17 Correct 180 ms 6304 KB Output is correct
18 Correct 1324 ms 6308 KB Output is correct
19 Correct 693 ms 6300 KB Output is correct
20 Correct 161 ms 6304 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -