Submission #1201923

#TimeUsernameProblemLanguageResultExecution timeMemory
1201923vincentbucourt1Let's Win the Election (JOI22_ho_t3)C++20
0 / 100
2597 ms4424 KiB
#include <bits/stdc++.h> using namespace std; void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);} #define int long long #define f first #define s second const int PREC = 1'000'000'000; int N, K; vector<pair<int,int>> vals; bool cmpVals (const pair<int,int>& a, const pair<int,int>& b) { if (a.s == -1) return false; else if (b.s == -1) return true; else return tie(a.s, a.f) < tie(b.s, b.f); } int dp[2][509][509]; int ans = (int)1e18; int test (int totalColab) { for (int numVote = 0; numVote <= K; numVote++) { for (int numColab = 0; numColab <= totalColab; numColab++) { dp[0][numVote][numColab] = (int)1e18; dp[1][numVote][numColab] = (int)1e18; } } dp[0][0][0] = 0; for (int idx = 0; idx < N; idx++) { for (int numVote = 0; numVote <= K; numVote++) { for (int numColab = 0; numColab <= totalColab; numColab++) { dp[(idx+1)%2][numVote][numColab] = (int)1e18; } } for (int numVote = 0; numVote <= K; numVote++) { for (int numColab = 0; numColab <= totalColab; numColab++) { int situOn = dp[idx%2][numVote][numColab]; if (situOn == (int)1e18) continue; dp[(idx+1)%2][numVote][numColab] = min(dp[(idx+1)%2][numVote][numColab], situOn); if (numVote+1 <= K) { dp[(idx+1)%2][numVote+1][numColab] = min(dp[(idx+1)%2][numVote+1][numColab], situOn + (PREC * vals[idx].f)/(totalColab+1)); } if (numVote+1 <= K && numColab+1 <= totalColab && vals[idx].s != -1) { dp[(idx+1)%2][numVote+1][numColab+1] = min(dp[(idx+1)%2][numVote+1][numColab+1], situOn + (PREC * vals[idx].s)/(numColab+1)); } } } } return dp[N%2][K][totalColab]; } signed main() { fastIO(); cin >> N >> K; vals.resize(N); for (int i = 0; i < N; i++) { cin >> vals[i].f >> vals[i].s; } sort(vals.begin(), vals.end(), cmpVals); for (int numColab = 0; numColab <= K; numColab++) { ans = min(ans, test(numColab)); } cout << ans/PREC << "." << ans%PREC << "\n"; }
#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...