Submission #1084604

#TimeUsernameProblemLanguageResultExecution timeMemory
1084604GasmaskChanLet's Win the Election (JOI22_ho_t3)C++17
0 / 100
586 ms996432 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAX = 5e2 + 5; pair<int, int> state[MAX]; double f[MAX][MAX][MAX]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) cin >> state[i].first >> state[i].second; sort(state + 1, state + n + 1, [](const pair<int, int> &a, const pair<int, int> &b) -> bool { if (a.second != -1 && b.second != -1) { return a.second < b.second; } return a.second > b.second; }); for (int i = 0; i <= n; i++) { for (int j = 0; j <= n + 1; j++) { for (int z = 0; z <= k; z++) { f[i][j][z] = 1e9; } } } f[0][1][0] = 0.0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i + 1; j++) { for (int z = 1; z <= k; z++) { f[i][j][z] = min(f[i - 1][j][z - 1] + (1.0 * state[i].first / j), f[i - 1][j][z]); if (j > 1 && state[i].second != -1) { f[i][j][z] = min(f[i][j][z], f[i - 1][j - 1][z - 1] + (1.0 * state[i].first / (j - 1)) + (1.0 * (state[i].second - state[i].first) / (j - 1))); } } } } double ans = 1e9; for (int j = 1; j <= n + 1; j++) { ans = min(ans, f[n][j][k]); } cout << fixed << ans; 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...