Submission #973699

#TimeUsernameProblemLanguageResultExecution timeMemory
973699berrLet's Win the Election (JOI22_ho_t3)C++17
5 / 100
2530 ms2396 KiB
#include <bits/stdc++.h> using namespace std; const int N = 505; double dp[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); int c=0; for(auto &[i, l]: a) cin >> i >> l, c+=(l!=-1); 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]; }); vector<double> val(n, -1); auto calc=[&](int e){ if(val[e]!=-1) return val[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<n; i++){ for(int l=e; l>=0; l--){ for(int x=n; x>=0; x--){ // cout<<(double)a[i][1]/(double)(l+1)<<"\n"; if(a[i][1]!=-1) dp[l+1][x] =min<double>(dp[l+1][x], dp[l][x]+(double)a[i][1]/(double)(l+1)); dp[l][x+1]=min<double>(dp[l][x+1], dp[l][x]+((double)a[i][0]/(double)(e+1))); } } } return val[e]=dp[e][k-e]; }; double ans=1e9; int s=0; for(int i=9; i>=0; i--){ int tmp = s+(1<<i); if(tmp<=k&&tmp<=c && calc(tmp)<calc(tmp-1)){ s=tmp; ans=min(ans, calc(tmp)); } } for(int i=max(0,s-10); i<=min(min(k, c), s+10); i++){ ans=min(ans, calc(i)); } 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...