Submission #973590

#TimeUsernameProblemLanguageResultExecution timeMemory
973590berrLet's Win the Election (JOI22_ho_t3)C++17
0 / 100
1091 ms8404 KiB
#include <bits/stdc++.h> using namespace std; const int N = 505; array<double, 2> dpold[N][N], dpnew[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]; }); for(int i=0; i<=n+1; i++){ for(int l=0; l<=n+1; l++){ dpold[i][l]={1e9, 1e9}; } } dpold[0][0]={0, 0}; for(int i=0; i<n; i++){ for(int i=0; i<=n+1; i++){ for(int l=0; l<=n+1; l++){ dpnew[i][l]={1e9, 1e9}; } } for(int l=n; l>=0; l--){ for(int x=n; x>=0; x--){ // cout<<(double)a[i][1]/(double)(l+1)<<"\n"; dpnew[l+1][x]=min(dpnew[l+1][x], {dpold[l][x][0]+(double)a[i][1]/(double)(l+1), dpold[l][x][1]}); dpnew[l][x+1]=min(dpnew[l][x+1], {dpold[l][x][0], dpold[l][x][1]+(double)a[i][0]}); } } for(int i=0; i<=n+1; i++){ for(int l=0; l<=n+1; l++){ dpold[i][l]=min(dpold[i][l], dpnew[i][l]); } } } double ans=1e9; for(int i=0; i<=k; i++){ ans=min(ans, dpold[i][k-i][0]+(double)dpold[i][k-i][1]/(double)(i+1)); } cout<<setprecision(9)<<fixed<<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...