Submission #761507

#TimeUsernameProblemLanguageResultExecution timeMemory
761507raysh07Let's Win the Election (JOI22_ho_t3)C++17
10 / 100
469 ms4520 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)1e18 #define f first #define s second mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); void Solve() { int n, k; cin >> n >> k; vector <pair<int, int>> a(n); for (auto &x : a){ cin >> x.f >> x.s; swap(x.f, x.s); if (x.f == -1) x.f = INF; } sort(a.begin(), a.end()); vector<vector<double>> dp(k + 1, vector<double>(k + 1, INF)); dp[0][0] = 0; for (auto x : a){ // cout << x.f << " " << x.s << "\n"; vector<vector<double>> ndp(k + 1, vector<double>(k + 1, INF)); for (int i = 0; i <= k; i++){ for (int j = 0; j <= i; j++){ ndp[i][j] = min(ndp[i][j], dp[i][j]); if (i != k){ ndp[i + 1][j] = min(ndp[i + 1][j], dp[i][j] + (double)x.s / (j + 1)); if (x.f < 1001) ndp[i + 1][j + 1] = min(ndp[i + 1][j + 1], dp[i][j] + (double)x.f / (j + 1)); } } } dp = ndp; // for (int i = 0; i <= k; i++){ // for (int j = 0; j <= k; j++){ // cout << dp[i][j] << " "; // } // cout << "\n"; // } // cout << "\n"; } double mn = INF; for (int i = 0; i <= k; i++) mn = min(mn, dp[k][i]); cout << fixed << setprecision(10) << mn << "\n"; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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...