Submission #825867

#TimeUsernameProblemLanguageResultExecution timeMemory
825867vjudge1Let's Win the Election (JOI22_ho_t3)C++17
77 / 100
1101 ms8628 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 500; const ld INF = 1e16; int n, k; pair<ld, ld> c[N + 10]; bool is1Subtask = 1; int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> c[i].first >> c[i].second; if(c[i].second == -1) c[i].second = INF; is1Subtask &= (c[i].second == c[i].first || c[i].second == INF); } sort(c + 1, c + n + 1, [](pair<ld, ld> x, pair<ld, ld> y) {return x.second < y.second;}); if(is1Subtask) { vector<vector<ld>> dp(n + 1, vector<ld>(n + 1, INF)); dp[0][1] = 0; for(int i = 1; i <= n; i++) { vector<vector<ld>> newdp = dp; for(int k = 1; k <= i; k++) { for(int v = 1; v <= i + 1; v++) { newdp[k][v] = min(newdp[k][v], dp[k - 1][v] + c[i].first / v); if(v > 1 && c[i].second != INF) newdp[k][v] = min(newdp[k][v], dp[k - 1][v - 1] + c[i].second / (v - 1)) ; } } dp = newdp; } ld res = INF; for(int v = 1; v <= n; v++) { res = min(res, dp[k][v]); } cout << setprecision(9) << fixed << res ; return 0; } if(n <= 100) { ld ans = INF; for(int t = 0; t <= k; t++) { vector<vector<ld>> dp(t + 1, vector<ld>(k - t + 1, INF)); dp[0][0] = 0; for(int i = 1; i <= n; i++) { vector<vector<ld>> newdp = dp; for(int j = 0; j <= t; j++) { for(int l = 0; l <= k - t; l++) { if(j) newdp[j][l] = min(newdp[j][l], dp[j - 1][l] + c[i].second / j); if(l) newdp[j][l] = min(newdp[j][l], dp[j][l - 1] + c[i].first / (t + 1)); } } dp = newdp; } ans = min(ans, dp[t][k - t]); } cout << setprecision(9) << fixed << ans ; return 0; } if(n == k) { ld res = INF; for(int t = 0; t <= n; t++) { vector<ld> dp(t + 1, INF); dp[0] = 0; for(int i = 1; i <= n; i++) { vector<ld> newdp(t + 1, INF); for(int j = 0; j <= t; j++) { newdp[j] = min(newdp[j], dp[j] + c[i].first / (t + 1)); if(j) newdp[j] = min(newdp[j], dp[j - 1] + c[i].second / j); } dp = newdp; } res = min(res, dp[t]); } cout << setprecision(9) << fixed << res ; 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...