Submission #1248844

#TimeUsernameProblemLanguageResultExecution timeMemory
1248844arashmemarLet's Win the Election (JOI22_ho_t3)C++20
10 / 100
522 ms984772 KiB
#include <bits/stdc++.h> using namespace std; pair <float, float> mn(pair <float, float> a, pair <float, float> b) { if (a.first + a.second < b.first + b.second) { return a; } return b; } const int maxn = 501; pair <int, int> a[maxn]; pair <float, float> dp[maxn][maxn][maxn]; int main() { cout << setprecision(20); int n, k; cin >> n >> k; for (int i = 1;i <= n;i++) { cin >> a[i].second >> a[i].first; if (a[i].first == -1) { a[i].first = maxn * maxn * maxn; } } sort(a + 1 , a + n + 1); for (int x = 0;x <= n;x++) { for (int i = 0;i <= n;i++) { for (int j = 0;j <= n;j++) { dp[x][i][j] = {1e18, 1e18}; } } } dp[0][0][0] = {0, 0}; float ans = 1e18; for (int i = 1;i <= n;i++) { for (int x = 0;x <= k;x++) { for (int xp = max(0, k - x - n + i);xp <= min(i - x, k - x);xp++) { dp[i][x][xp] = dp[i - 1][x][xp]; if (x) { dp[i][x][xp] = mn(dp[i][x][xp], {dp[i - 1][x - 1][xp].first + (float)a[i].first / x, dp[i - 1][x - 1][xp].second * ((double)x / (x + 1))}); } if (xp) { dp[i][x][xp] = mn(dp[i][x][xp], {dp[i - 1][x][xp - 1].first, dp[i - 1][x][xp - 1].second + (float)a[i].second / (x + 1)}); } } } } for (int i = 0;i <= k;i++) { for (int j = 0;j <= k;j++) { if (i + j == k) { ans = min(ans, dp[n][i][j].first + dp[n][i][j].second); } } } cout << ans; }
#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...