Submission #1211161

#TimeUsernameProblemLanguageResultExecution timeMemory
1211161VMaksimoski008Let's Win the Election (JOI22_ho_t3)C++20
100 / 100
1386 ms4164 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int n, x, cnt=0; vector<array<ll, 2> > a; double dp[2][505][505]; double f(int c) { for(int i=0; i<2; i++) for(int j=0; j<=x-c; j++) for(int k=0; k<=c; k++) dp[i][j][k] = 1e18; dp[0][0][0] = 0; for(int i=1; i<=n; i++) { int p = i&1; for(int j=0; j<=x-c; j++) { for(int k=0; k<=c; k++) { dp[p][j][k] = dp[p^1][j][k]; if(j) dp[p][j][k] = min(dp[p][j][k], dp[p^1][j-1][k] + (double)a[i][1] / (1 + c)); if(k && a[i][0] != -1) dp[p][j][k] = min(dp[p][j][k], dp[p^1][j][k-1] + (double)a[i][0] / k); } } } return dp[n&1][x-c][c]; } signed main() { cin >> n >> x; a.resize(n+1); for(int i=1; i<=n; i++) { cin >> a[i][1] >> a[i][0]; if(a[i][0] != -1) cnt++; } sort(a.begin()+1, a.end()); int l=0, r=min(x, cnt)-1, p = min(x, cnt); while(l <= r) { int mid = (l + r) / 2; if(f(mid) <= f(mid+1)) p = mid, r = mid - 1; else l = mid + 1; } cout << setprecision(3) << fixed << f(p) << '\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...