Submission #528174

#TimeUsernameProblemLanguageResultExecution timeMemory
528174dooweyLet's Win the Election (JOI22_ho_t3)C++14
100 / 100
1719 ms6988 KiB
#include <bits/stdc++.h> using namespace std; typedef long double ld; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 505; const ld inf = 1e12; vector<ld> suff[N]; ld A[N]; ld B[N]; ld dp[N][N]; void mini(ld &a, ld b){ a = min(a, b); } int main(){ fastIO; //freopen("in.txt","r",stdin); int n, k; cin >> n >> k; vector<pair<ld,ld>> C(n); for(int i = 0 ; i < n; i ++ ){ cin >> C[i].se >> C[i].fi; if(C[i].fi == -1) C[i].fi = inf; } sort(C.begin(), C.end()); for(int i = 0 ; i < n; i ++ ){ A[i + 1] = C[i].se; B[i + 1] = C[i].fi; } for(int i = n; i >= 1; i -- ){ for(int j = i ; j <= n; j ++ ){ suff[i].push_back(A[j]); } sort(suff[i].begin(), suff[i].end()); } ld res = inf; ld current; for(int take = 0; take <= k ; take ++ ){ for(int i = 0 ; i <= n; i ++ ){ for(int j = 0 ; j <= n; j ++ ){ dp[i][j] = inf; } } dp[0][0] = 0; for(int i = 1; i <= n; i ++ ){ for(int j = 0 ; j <= i ; j ++ ){ if(dp[i - 1][j] == inf) continue; mini(dp[i][j], dp[i-1][j] + A[i] / ld(take + 1)); mini(dp[i][j+1], dp[i-1][j] + B[i] / ld(j + 1)); } } for(int id = take; id <= k; id ++ ){ current = dp[id][take]; for(int j = 0 ; j < k - id; j ++ ){ current += suff[id + 1][j] / ld(take + 1); } res = min(res, current); } } cout << fixed << setprecision(9) << res << "\n"; 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...