Submission #1210333

#TimeUsernameProblemLanguageResultExecution timeMemory
1210333ByeWorldLet's Win the Election (JOI22_ho_t3)C++20
23 / 100
2595 ms488 KiB
#include <bits/stdc++.h> #define int long long #define ll long long #define fi first #define se second #define lf ((id<<1)) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define pb push_back #define ld long double using namespace std; const int MAXN = 2e5+10; const ld INF = 5e5+10; typedef pair<ll,ll> pii; void chmn(auto &a, auto b){ a = min(a, b); } int n, k; int a[MAXN], b[MAXN]; int done[MAXN], day; ld ans = INF; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>k; vector<pii> tot; for(int i=1; i<=n; i++){ cin>>a[i]>>b[i]; if(b[i] != -1) tot.pb({b[i], i}); } for(int ma=0; ma<(1<<n); ma++){ vector<pii> tot; vector<int> vec; for(int i=1; i<=n; i++){ if(b[i] != -1 && ((ma>>(i-1)) & 1)) tot.pb({b[i], i}); else vec.pb(a[i]); } sort(tot.begin(), tot.end()); sort(vec.begin(), vec.end()); day++; ld te = 0; int num = 1, vote = 0; // ambil col-1 awal for(auto [tim, id] : tot){ if(vote == k) break; te += (ld)tim/num; num++; vote++; } for(int i=0; i<vec.size(); i++){ if(vote == k) break; te += (ld)vec[i]/num; vote++; } chmn(ans, te); } // sort(tot.begin(), tot.end()); // for(int col=0; col<=tot.size(); col++){ // number of collaborator // day++; // ld te = 0; int num = 1; // // ambil col-1 awal // for(int i=0; i<=col-1; i++){ // done[tot[i].se] = day; // te += (ld)tot[i].fi/num; // num++; // } // vector<int> vec; // for(int i=1; i<=n; i++){ // if(done[i] == day) continue; // vec.pb(a[i]); // } // sort(vec.begin(), vec.end()); // for(int i=0; i<k-col; i++) // te += (ld)vec[i]/num; // chmn(ans, te); // } cout << fixed << setprecision(7) << ans << '\n'; }
#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...