Submission #1210555

#TimeUsernameProblemLanguageResultExecution timeMemory
1210555ByeWorldLet's Win the Election (JOI22_ho_t3)C++20
61 / 100
2596 ms9152 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") // #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<int,int> 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[3][510][510]; ld coba(int col){ for(int i=0; i<=2; i++) for(int take=0; take<=col; take++) // ambil b for(int oth=0; oth<=k-col; oth++) // ambil a dp[i][take][oth] = INF; dp[0][0][0] = 0; for(int i=1; i<=n; i++){ for(int take=0; take<=col; take++){ for(int oth=0; oth<=k-col; oth++){ // gk ambil samsek dp[i%2][take][oth] = dp[(i-1)%2][take][oth]; // ambil a if(oth>=1) dp[i%2][take][oth] = min(dp[i%2][take][oth], dp[(i-1)%2][take][oth-1] + (ld)a[i]/(col+1)); // ambil b if(take>=1) dp[i%2][take][oth] = min(dp[i%2][take][oth], dp[(i-1)%2][take-1][oth] + (ld)b[i]/take ); } } } // cout << col << ' ' << dp[n][col] << " pp\n"; return dp[n%2][col][k-col]; } 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]; int l = 0, r = k, mid1, mid2; while(r-l>=3){ mid1 = (l+l+r)/3; mid2 = (l+r+r+2)/3; ld le = coba(mid1), ri = coba(mid2); ans = min(ans, min(le, ri)); if(le < ri) r = mid2; else l = mid1; } for(int i=l; i<=r; i++) ans = min(ans, coba(i)); 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...