Submission #924030

#TimeUsernameProblemLanguageResultExecution timeMemory
924030goodspeed0208Let's Win the Election (JOI22_ho_t3)C++14
100 / 100
400 ms3056 KiB
#include<bits/stdc++.h> #define pii pair<int, int> #define INF 5000000 using namespace std; bool cmp(pii a, pii b) { if (a.second == -1 && b.second == -1) return a.first < b.first; if (a.second == -1) return (1 > 2); if (b.second == -1) return (1 < 2); if (a.second == b.second) return a.first > b.first; return a.second < b.second; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, K; cin >> n >> K; vector<pii>v(n+1); vector<double>a(n+1), b(n+1); for (int i = 1 ; i <= n ;i++) cin >> v[i].first >> v[i].second; sort(v.begin()+1, v.end(), cmp); for (int i = 1 ; i <= n ;i++) a[i] = (double)v[i].first, b[i] = (double)v[i].second; //vector<vector<vector<double> > >dp(505, vector<vector<double> >(505, vector<double>(505, INF)) ); //dp[0][0][1] = 0.0; double ans = INF; multiset<int>st; vector<double>w(n+2, 0); for (int i = n ; i >= 1 ; i--) { st.insert(a[i]); int k = 0; for (auto j : st) { if (k >= K-(i-1)) break; w[i] += j; k++; } } //for (int i = 1 ; i <= n ; i++) cout << w[i] << " "; //cout << "\n"; ans = w[1]; for (int help = 1 ; help <= K+1 ; help++) { vector<vector<double> >dp(505, vector<double>(505, INF)); dp[0][1] = 0; //cout << "help" << " " << help << ": \n"; for (int i = 1 ; i <= n ; i++) {//first i people //cout << i << ": "; for (int k = 1 ; k <= min(i+1, help) ; k++) {// get how many people dp[i][k] = dp[i-1][k] + (a[i] / help); if (k > 1 && b[i] != -1) dp[i][k] = min(dp[i][k], dp[i-1][k-1] + b[i] / (k-1)); //cout << dp[i][k] <<" "; if (k == help) { ans = min(ans, dp[i][help] + w[i+1] / help); //cout << "ans: " << dp[i][help] << "+" << w[i+1] / help << "\n"; } } //cout << "\n"; } //for (int i = 0) } cout << fixed << setprecision(6) << ans << "\n"; //for (auto &i : v) cout << i.first <<" " << i.second << "\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...