Submission #973978

#TimeUsernameProblemLanguageResultExecution timeMemory
973978berrLet's Win the Election (JOI22_ho_t3)C++17
5 / 100
176 ms4444 KiB
#include <bits/stdc++.h> using namespace std; const int N = 505; double dp[N][N], mi[N][N]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<array<int, 2>> a(n); for(auto &[i, l]: a) cin >> i >> l; sort(a.begin(), a.end(), [&](auto x, auto y){ if(x[1]==y[1]) return x[0] < y[0]; else if(y[1]==-1) return true; else if(x[1]==-1) return false; return x[1]<y[1]; }); double ans=1e9; for(int i=0; i<=n; i++){ for(int l=0; l<=n; l++){ mi[i][l]=1e9; } } mi[n][0]=0; for(int i=n-1; i>=0; i--){ mi[i][0]=0; for(int l=n; l>0; l--){ mi[i][l]=min(mi[i][l], mi[i+1][l-1]+a[i][0]); /// cout<<mi[i+1][l-1]<<" "<<mi[i][l]<<"\n"; } } auto calc=[&](int e){ for(int i=0; i<=n+1; i++){ for(int l=0; l<=n+1; l++){ dp[i][l]=1e9; } } dp[0][0]=0; for(int i=0; i<=k; i++){ if(a[i][1]==-1) break; dp[i][0]=(i==0?0:dp[i-1][0])+(double)a[i][0]/(double)(e+1); if(i>0) for(int l=e; l>=1; l--) dp[i][l] =min<double>(dp[i-1][l-1]+(double)a[i][1]/(double)(l), dp[i-1][l]+((double)a[i][0])/(double)(e+1)); else dp[i][1]=a[i][1], dp[i][0]=(double)a[i][0]/(e+1); } for(int i=0; i<=k; i++){ if(mi[i+1][k-i-1]!=1e9) ans=min(ans, dp[i][e]+(double)mi[i+1][k-i-1]/(double)(e+1)); } }; for(int i=1; i<=k; i++){ calc(i); } ans=min(ans, mi[0][k]); cout<<setprecision(9)<<ans<<"\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...