oj.uz

Submission #734545

# Submission time Handle Problem Language Result Execution time Memory
734545 2023-05-02T15:37:07 Z 1075508020060209tc Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 28 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;
#define double long double
int n;int K;
int M;
int ar[200005];
int br[200005];
double ans;


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){

vector<pair<int,int>>tar;
for(int i=1;i<=n;i++){
    tar.push_back({ar[i],br[i]});
}
sort(tar.begin(),tar.end(),cmp);
vector<pair<int,int>>anv;
for(int i=0;i<m;i++){
    anv.push_back(tar[i]);
}
vector<int>tv;
for(int i=m;i<n;i++){
    tv.push_back(tar[i].first);
}
sort(tv.begin(),tv.end());
/*
for(int i=0;i<tar.size();i++){
    cout<<tar[i].first<<"_"<<tar[i].second<<endl;
}*/

double ret=0;
for(int i=0;i<K-m;i++){
    ret+=(double)tv[i]/(double)(m+1);
}
for(int i=0;i<anv.size();i++){
    ret+=(double)anv[i].second/(double)(i+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]>>br[i];
    if(br[i]!=-1){
        M++;
    }else{
        br[i]=2000;
    }
}
ans=500000;
for(int i=0;i<=min(K,M);i++){
    ans=min(ans,solve(i));
  //  cout<<endl<<endl;
}
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;


*/

}

Compilation message

Main.cpp: In function 'long double solve(int)':
Main.cpp:44:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 | for(int i=0;i<anv.size();i++){
      |             ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 9 ms 324 KB Output is correct
13 Correct 8 ms 212 KB Output is correct
14 Correct 5 ms 308 KB Output is correct
15 Correct 14 ms 340 KB Output is correct
16 Correct 14 ms 212 KB Output is correct
17 Correct 6 ms 336 KB Output is correct
18 Correct 21 ms 324 KB Output is correct
19 Correct 16 ms 324 KB Output is correct
20 Correct 5 ms 320 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 9 ms 324 KB Output is correct
13 Correct 8 ms 212 KB Output is correct
14 Correct 5 ms 308 KB Output is correct
15 Correct 14 ms 340 KB Output is correct
16 Correct 14 ms 212 KB Output is correct
17 Correct 6 ms 336 KB Output is correct
18 Correct 21 ms 324 KB Output is correct
19 Correct 16 ms 324 KB Output is correct
20 Correct 5 ms 320 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Incorrect 0 ms 212 KB Output isn't correct
30 Halted 0 ms 0 KB -