Submission #1276226

#TimeUsernameProblemLanguageResultExecution timeMemory
1276226namhhLet's Win the Election (JOI22_ho_t3)C++20
100 / 100
92 ms2424 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second const int N = 5e2+5; int n,k; double dp[N][N]; pii a[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; for(int i = 1; i <= n; i++){ cin >> a[i].fi >> a[i].se; swap(a[i].fi,a[i].se); if(a[i].fi == -1) a[i].fi = 1e9; } sort(a+1,a+n+1); double ans = 1e9; for(int t = 0; t <= k; t++){ int kaori = k-t; for(int i = 0; i <= n; i++){ for(int j = 0; j <= min(i,kaori); j++) dp[i][j] = 1e9; } dp[0][0] = 0; for(int i = 1; i <= n; i++){ for(int j = 0; j <= min(i,kaori); j++){ if(j > 0) dp[i][j] = min(dp[i][j],dp[i-1][j-1]+(double)a[i].se/(t+1)); if(i > j && i-j <= t) dp[i][j] = min(dp[i][j],dp[i-1][j]+(double)a[i].fi/(i-j)); else if(i-j > t) dp[i][j] = min(dp[i][j],dp[i-1][j]); } } ans = min(ans,dp[n][kaori]); } cout << fixed << setprecision(18) << ans; }
#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...