Submission #1023209

#TimeUsernameProblemLanguageResultExecution timeMemory
1023209snpmrnhlolLet's Win the Election (JOI22_ho_t3)C++17
100 / 100
1597 ms4444 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll N = 5e2; const ll inf = 1e18; struct state{ ll a,b; }v[N]; int p[N]; ld dp[N + 1][N + 1]; ll sum[N + 1]; vector<int> v2; int main(){ cout<<fixed<<setprecision(5); int n,k; ld ans = inf; cin>>n>>k; for(int i = 0;i < n;i++){ cin>>v[i].a>>v[i].b; if(v[i].b == -1)v[i].b = inf; p[i] = i; } sort(p,p + n,[&](int a, int b){ return v[a].b < v[b].b; }); for(int i = n;i >= 0;i--){ ///first i - 1 complete v2.clear(); for(int j = i;j < n;j++){ v2.push_back(v[p[j]].a); } sort(v2.begin(),v2.end()); for(int j = 0;j < k - i;j++){ sum[i]+=v2[j]; } } for(int m = 0;m < k;m++){ for(int i = 0;i <= n;i++){ for(int j = 0;j <= n;j++){ dp[i][j] = inf; } } dp[0][0] = 0;///i as j bs for(int i = 0;i <= n;i++){ int id = p[i]; for(int j = 0;j <= i;j++){ if(i - j + 1 <= n)dp[i - j + 1][j] = min(dp[i - j + 1][j],dp[i - j][j] + (ld)v[id].a/(m + 1)); if(j + 1 <= n)dp[i - j][j + 1] = min(dp[i - j][j + 1],dp[i - j][j] + (ld)v[id].b/(j + 1)); } } for(int i = 0;i + m <= n;i++){ ans = min(ans,dp[i][m] + (ld)sum[i + m]/(m + 1)); } } cout<<ans; return 0; } /** 7 5 284 758 x 474 288 668 380 320 635 315 333 702 x 369 374 676 302 375 666 x 291 393 646 x 253 **/
#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...