Submission #1248840

#TimeUsernameProblemLanguageResultExecution timeMemory
1248840arashmemarLet's Win the Election (JOI22_ho_t3)C++20
0 / 100
407 ms492592 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 501; pair <int, int> a[maxn]; 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; } } } dp[0][0][0] = 0; float ans = 1e18; for (int c = k / 2;c <= k;c++) { for (int i = 1;i <= n;i++) { for (int x = 0;x <= min(i, c);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 + xp > i - 1) { dp[i][x][xp] = 1e18; } if (x) { dp[i][x][xp] = min(dp[i][x][xp], dp[i - 1][x - 1][xp] + (float)a[i].first / x); } if (xp) { dp[i][x][xp] = min(dp[i][x][xp], dp[i - 1][x][xp - 1] + (float)a[i].second / (c + 1)); } } } } ans = min(ans, dp[n][c][k - c]); } 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...