Submission #973990

#TimeUsernameProblemLanguageResultExecution timeMemory
973990berrLet's Win the Election (JOI22_ho_t3)C++17
0 / 100
2 ms4440 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+1][l], mi[i+1][l-1]+a[i][0]); } } auto calc=[&](int e){ for(int i=0; i<=n+1; i++){ for(int l=0; l<=n+1; l++){ dp[i][l]=1e9; } } 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]; } cout<<dp[0][1]<<" "<<mi[1][2]; for(int i=0; i<k; i++){ if(mi[i+1][k-i-1]!=1e9&&dp[i][e]!=(1e9)) ans=min(ans, dp[i][e]+(double)mi[i+1][k-i-1]/(double)(e+1)); } }; for(int i=1; i<=1; i++){ calc(i); } ans=min(ans, mi[0][k]); cout<<fixed<<" "<<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...