Submission #1240662

#TimeUsernameProblemLanguageResultExecution timeMemory
1240662GeforgsLet's Win the Election (JOI22_ho_t3)C++20
10 / 100
201 ms488 KiB
#include <iostream> #include <iomanip> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <map> #include <unordered_map> #include <stack> #include <bitset> #include <string> #include <cstring> #include <iterator> #include <random> #define ll long long #define ld long double #define inf (ll)(2*1e18) #define sort(a) sort(a.begin(), a.end()) #define reverse(a) reverse(a.begin(), a.end()) #define pb push_back #define endl "\n" using namespace std; void solve(){ ll n, k, i, x, w, cnt, left, j; ld res=inf, ans, ans2; cin>>n>>k; vector<pair<ll, ll>> a(n); multiset<ll> s; for(i=0;i<n;++i){ cin>>x>>w; if(w == -1) w = inf; a[i] = {x, w}; } sort(a); // for(i=0;i<k;++i){ // res += *s.begin(); // s.erase(s.begin()); // } // for(i=0;i<n;++i){ // if(a[i].first == inf or i == k) break; // s.clear(); // ans = 0; // cnt = 1; // for(j=0;j<=i;++j){ // ans += (ld)a[j].first/(ld)cnt; // ++cnt; // } // for(;j<n;++j){ // s.insert(a[j].second); // } // for(j=i+1;j<k;++j){ // ans += (ld)*s.begin()/(ld)cnt; // s.erase(s.begin()); // } // res = min(res, ans); // } // for(i=0;i<n;++i){ // swap(a[i].first, a[i].second); // } // sort(a); for(i=0;i<k;++i){ s.clear(); ans = 0; cnt = 1; vector<pair<ll, ll>> c; for(j=0;j<=i;++j){ ans += (ld)a[j].first/(ld)(k - i); if(a[j].second != inf) c.pb({a[j].second-a[j].first, a[j].first}); } sort(c); ans2 = ans*(k - i); for(;j<n;++j){ s.insert(a[j].second); } while(s.size() > k - i - 1){ s.erase(--s.end()); } for(auto el: s){ ans += (ld)el/(ld)cnt; } res = min(res, ans); for(auto [y, val]: c){ s.insert(y+val); ans2 -= val; ans = ans2/(ld)(cnt + 1); cnt = 1; for(auto el: s){ ans += (ld)el/(ld)cnt; ++cnt; } res = min(res, ans); } } cout<<fixed<<setprecision(20)<<res<<endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); srand(time(nullptr)); ll t=1; // cin>>t; for(;t>0;--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...