Submission #1182910

#TimeUsernameProblemLanguageResultExecution timeMemory
1182910dima2101Let's Win the Election (JOI22_ho_t3)C++20
11 / 100
1451 ms4376 KiB
#include <bits/stdc++.h> #define int long long const int MAXN = 501; long double dp[MAXN][MAXN]; int32_t main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n; std::cin >> n; int k; std::cin >> k; std::vector<std::pair<int, int>> b(n); int cnt = 0; bool tmp = true; for (int i = 0; i < n; i++) { std::cin >> b[i].first; std::cin >> b[i].second; if (b[i].second == -1) { cnt++; b[i].second = 1e4; } } std::sort(b.begin(), b.end(), [&](std::pair<int, int> a, std::pair<int, int> b) { return a.second < b.second; }); long double ans = 1e18; for (int z = 0; z <= k; z++) { for (int i = 0; i < MAXN; i++) { for (int j = 0; j < MAXN; j++) { dp[i][j] = 1e18; } } dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= n; j++) { // dp[i][j] = dp[i - 1][j]; if (j > 0 && b[i - 1].second != 1e4) { // std::cout << i << ' ' << b[i - 1].second << std::endl; dp[i][j] = std::min( dp[i][j], dp[i - 1][j - 1] + (long double)(b[i - 1].second) / (long double)(j)); } if (k > 0) { dp[i][j] = std::min(dp[i][j], dp[i - 1][j] + (long double)(b[i - 1].first) / (long double)(z + 1)); } } } // std::cout << z << ' ' << dp[n][z][k - z] << std::endl; ans = std::min(ans, dp[n][z]); } std::cout << std::setprecision(20) << std::fixed << 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...