Submission #880014

#TimeUsernameProblemLanguageResultExecution timeMemory
880014frostray8653Let's Win the Election (JOI22_ho_t3)C++17
100 / 100
613 ms3108 KiB
#include <bits/stdc++.h> #define int long long #define IO ios::sync_with_stdio(0), cin.tie(0) #define FOR(i, a, b) for (int i = a; i <= b; i++) using namespace std; using pii = pair<int, int>; const int N = 505; const int INF = 1e9; const double dINF = 1e9; pii a[N]; int n, tar; /// 共有 cnt 個助選人 double calc(int cnt) { vector<vector<double>> dp(n + 1, vector<double>(n + 1, dINF)); dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = tar; j >= 1; j--) dp[j][cnt] = min(dp[j][cnt], dp[j - 1][cnt] + (double)a[i].first / (cnt + 1)); for (int j = cnt; j >= 0; j--) { if (j != cnt) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (double)a[i].first / (cnt + 1)); if (j && a[i].second < INF) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (double)a[i].second / j); } } return dp[tar][cnt]; } signed main() { IO; cin >> n >> tar; FOR(i, 1, n) { cin >> a[i].first >> a[i].second; if (a[i].second == -1) a[i].second = INF; } sort(a + 1, a + n + 1, [&](pii p, pii q) { return p.second < q.second; }); double ans = dINF; for (int i = 0; i <= tar; i++) ans = min(ans, calc(i)); cout << fixed << setprecision(15) << ans << "\n"; 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...