Submission #858907

#TimeUsernameProblemLanguageResultExecution timeMemory
858907HanksburgerLet's Win the Election (JOI22_ho_t3)C++17
100 / 100
167 ms4440 KiB
#include <bits/stdc++.h> using namespace std; pair<double, double> a[505]; double dp[505][505][2]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; for (int i=1; i<=n; i++) { cin >> a[i].second >> a[i].first; if (a[i].first==-1) a[i].first=1e9; } sort(a+1, a+n+1); double ans=1e9; for (int m=0; m<=k; m++) { for (int i=0; i<=n; i++) for (int j=0; j<=k-m; j++) dp[i][j][0]=dp[i][j][1]=1e9; dp[0][0][1-(bool)m]=0; for (int i=1; i<=n; i++) { for (int j=0; j<=min(i, k-m); j++) { if (i-j<m) { if (!j) dp[i][j][0]=dp[i-1][j][0]+a[i].first/(i-j); else if (j==i) dp[i][j][0]=dp[i-1][j-1][0]+a[i].second/(m+1); else dp[i][j][0]=min(dp[i-1][j][0]+a[i].first/(i-j), dp[i-1][j-1][0]+a[i].second/(m+1)); } else { dp[i][j][1]=dp[i-1][j][1]; if (j) dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][1]+a[i].second/(m+1)); if (i-j==m) dp[i][j][1]=min(dp[i][j][1], dp[i-1][j][0]+a[i].first/m); } } } ans=min(ans, dp[n][k-m][1]); } cout << 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...