Submission #939854

#TimeUsernameProblemLanguageResultExecution timeMemory
939854TAhmed33Let's Win the Election (JOI22_ho_t3)C++98
0 / 100
800 ms766076 KiB
#include <bits/stdc++.h> using namespace std; typedef long double ld; int n, k, a[501], b[501]; ld dp[1 << 20][23]; ld recurse (int mask, int c, int l) { if (l == k) return 0; ld &ret = dp[mask][c]; if (ret == ret) return ret; ret = 1e18; for (int i = 0; i < n; i++) { if (mask & (1 << i)) continue; ret = min(ret, 1.0 * a[i] / c + recurse(mask ^ (1 << i), c, l + 1)); } int pos = -1, mx = 1e9; for (int i = 0; i < n; i++) { if (mask & (1 << i)) continue; if (b[i] != -1 && b[i] < mx) { mx = b[i]; pos = i; } } if (pos != -1) { ret = min(ret, 1.0 * b[pos] / c + recurse(mask ^ (1 << pos), c + 1, l + 1)); } return ret; } int main () { memset(dp, -1, sizeof(dp)); cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; cout << fixed << setprecision(9) << recurse(0, 1, 0) << '\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...