Submission #939309

#TimeUsernameProblemLanguageResultExecution timeMemory
939309LitusianoLet's Win the Election (JOI22_ho_t3)C++17
0 / 100
2532 ms796 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define endl "\n" const int INF = 1e18; mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count()); bool cmp(pair<int,int> a, pair<int,int> b){ if(a.second == b.second) return a.first>b.first; return a.second < b.second; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout<<setprecision(3)<<fixed; int n,k1; cin>>n>>k1; vector<pair<int,int>> v(n); for(int i = 0; i<n; i++){ cin>>v[i].first>>v[i].second; if(v[i].second == -1) v[i].second = INF; } long double ans = INF; for(int x = 0; x <= k1; x++){ int buy = k1-x; // cheaper way to buy buy vector<long double> dp(x+1, INF); vector<pair<int,int>> act = v; map<pair<int,int>, int> curinsum, curinb, tot; sort(act.begin(),act.end()); for(auto y : act) tot[y]++; dp[0] = 0; for(int i = 0; i<buy; i++) dp[0] += 1.0 * act[i].first / (x+1), curinsum[act[i]]++; sort(act.begin(),act.end(),cmp); for(int i = 1; i <= x; i++){ pair<int,int> bst; long double best = INF; pair<int,int> bst1; for(auto y : act){ if(y.second == -1) continue; // buying this if(tot[y] == curinb[y]) continue; // can make the transition if(tot[y] == curinb[y] + curinsum[y]){ // retreat from the sum long double cur = dp[i-1] - 1.0*y.first/(x+1) + 1.0*y.second/i; // now take the other minimum(just bruteforce for now) for(auto z : tot){ if(z.second == curinb[z.first] + curinsum[z.first]) continue; long double tmp = cur + 1.0*z.first.first/(x+1); if(tmp < best){ best = tmp; bst = y; bst1 = z.first; } } } else{ long double tmp = dp[i-1] + 1.0*y.second/(i); if(tmp < best){ best = tmp; bst = y; bst1 = {-1,-1}; } } } if(best == INF) continue; curinb[bst]++; if(bst1.first != -1) curinsum[bst]--,curinsum[bst1]++; dp[i] = best; } // cerr<<dp[x]<<" "; ans = min(ans, dp[x]); // having bought x collaborators } cout<<ans<<endl; }
#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...