Submission #1268102

#TimeUsernameProblemLanguageResultExecution timeMemory
1268102lambd47Let's Win the Election (JOI22_ho_t3)C++20
10 / 100
1 ms328 KiB
#include <bits/stdc++.h>

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define double long double

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod=1e9;
void solve() {
    int n,k;cin>>n>>k;

    vector<pair<int,int>> vec(n);
    L(i,0,n-1)cin>>vec[i].first>>vec[i].second;
    sort(all(vec));
    vector<int> ord;
    L(i,0,n-1){
        if(vec[i].second!=-1){
            ord.push_back(i);
        }
    }

    sort(all(ord),[&](int a,int b){
            return vec[a].second<vec[b].second;
            });
            

    double resp=mod;
    vector<bool> usei(n,0);
    L(i,0,sz(ord)){//usando quantos falantes
        int qnt=i+1;
        double respat=0;
        L(j,0,i-1){
            usei[ord[j]]=1;
            respat+=(double)vec[ord[j]].second/(j+1);
        }
        int id=0;
        int quero=k-i;
        while(quero>0){
            if(usei[id]){
                id++;continue;
            }
            respat+=(double)vec[id].first/qnt;
            quero--;
            id++;
        }
        resp=min(resp,respat);
    }
    cout<<setprecision(11);
    cout<<resp;




}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...