Submission #1085016

#TimeUsernameProblemLanguageResultExecution timeMemory
1085016GasmaskChanLet's Win the Election (JOI22_ho_t3)C++17
100 / 100
148 ms2552 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAX = 5e2 + 5; void minimize(double &a, const double &b) { a = min(a, b); } int sum[MAX][MAX]; double f[2][MAX]; pair<int, int> state[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; int g = 0; for (int i = 1; i <= n; i++) { cin >> state[i].first >> state[i].second; if (state[i].second == -1) state[i].second = 1e9; else ++g; } sort(state + 1, state + n + 1, [](const pair<int, int> &a, const pair<int, int> &b) -> bool { if (a.second != b.second) return a.second < b.second; return a.first < b.first; }); memset(sum, 0x3f, sizeof sum); for (int i = 1; i <= n; i++) { sum[i][0] = 0; for (int j = i; j <= n; j++) { for (int z = k; z > 0; z--) { sum[i][z] = min(sum[i][z], sum[i][z - 1] + state[j].first); } } } sum[n + 1][0] = 0; double ans = sum[1][k]; g = min(g, k); for (int c = 0; c <= g; c++) { for (int i = 0; i < 2; i++) { for (int j = 0; j <= k; j++) { f[i & 1][j] = 1e9; } } f[0][0] = 0.0; for (int i = 1; i <= k; i++) { for (int j = 0; j <= i; j++) { f[i & 1][j] = f[(i - 1) & 1][j] + 1.0 * state[i].first / (c + 1); if (j) minimize(f[i & 1][j], f[(i - 1) & 1][j - 1] + 1.0 * state[i].second / j); if (j == c) { minimize(ans, f[i & 1][j] + 1.0 * sum[i + 1][k - i] / (c + 1)); } } } } 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...