Submission #1210360

#TimeUsernameProblemLanguageResultExecution timeMemory
1210360ByeWorldLet's Win the Election (JOI22_ho_t3)C++20
11 / 100
644 ms4504 KiB
#include <bits/stdc++.h> #define int long long #define ll long long #define fi first #define se second #define lf ((id<<1)) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define pb push_back #define ld long double using namespace std; const int MAXN = 2e5+10; const ld INF = 1e9+10; typedef pair<ll,ll> pii; void chmn(auto &a, auto b){ a = min(a, b); } int n, k; int p[MAXN], q[MAXN], a[MAXN], b[MAXN]; ld ans = INF; ld dp[510][510]; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>k; vector<pii> vec; vec.pb({-1,-1}); for(int i=1; i<=n; i++){ cin>>p[i]>>q[i]; if(q[i] == -1) q[i] = MAXN; vec.pb({q[i], i}); } sort(vec.begin(), vec.end()); for(int i=1; i<=n; i++) a[i] = p[vec[i].se], b[i] = q[vec[i].se]; for(int col=0; col<=n; col++){ // colab for(int take=0; take<=col; take++) for(int i=0; i<=n; i++) dp[i][take] = INF; dp[0][0] = 0; for(int take=0; take<=col; take++){ for(int i=1; i<=n; i++){ dp[i][take] = dp[i-1][take] + (ld)a[i]/(col+1); // gk ambil // ambil if(take>=1) chmn(dp[i][take], dp[i-1][take-1] + (ld)b[i]/take ); } } // cout << col << ' ' << dp[n][col] << " pp\n"; chmn(ans, dp[n][col]); } cout << fixed << setprecision(7) << 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...