Submission #1233250

#TimeUsernameProblemLanguageResultExecution timeMemory
1233250ByeWorldLet's Win the Election (JOI22_ho_t3)C++20
100 / 100
990 ms6492 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #define int long long #define ll long long #define se second #define fi first #define pb push_back #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<pii,pii> ipii; const int MAXN = 510; const int MAXA = 5e5+10; const int SQRT = 450; const ld INF = 1e16; const int IN = 1e10; const int MOD = 1e9+7; const int LOG = 60; int sum(int a, int b){ return (a+MOD+b)%MOD; } void chsum(int &a, int b){ a = sum(a,b); } int mul(int a, int b){ return (a*b)%MOD; } void chmul(int &a, int b){ a = mul(a,b); } void chmn(auto &a, auto b){ a = min(a, b); } void chmx(auto &a, auto b){ a = max(a, b); } vector<int> dx = {0, 0, -1, 1}; vector<int> dy = {1, -1, 0, 0}; int n, need, a[MAXN], b[MAXN], su[510][510], blm[MAXN], cost[MAXN]; ld dp[510][510]; ld ANS = INF; void solve(int sp){ // sort based on b // dari belakang, tambahin b for(int i=0; i<=n+1; i++) for(int j=0; j<=n+1; j++) dp[i][j] = INF, su[i][j] = IN; dp[0][0] = 0; for(int i=1; i<=need; i++){ for(int j=0; j<=sp; j++){ // b yg udh diambil segini // ambil b, ambil a dp[i][j] = dp[i-1][j] + (ld)blm[i]/(sp+1); if(j!=0 && cost[i]!=INF){ // ambil chmn(dp[i][j], dp[i-1][j-1] + (ld)cost[i]/j); } } } su[n+1][0] = 0; for(int j=0; j<=n; j++){ for(int i=n; i>=1; i--){ su[i][j] = su[i+1][j]; if(j!=0) chmn(su[i][j], su[i+1][j-1]+blm[i]); } } // cout << fixed << setprecision(5) << dp[1][1] << "Xx\n"; // cout << ' ' << su[2][need-1] << " pp\n"; for(int i=sp; i<=need; i++){ chmn(ANS, dp[i][sp] + (ld)su[i+1][need-i] / (sp+1) ); } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>need; vector<pii> cc; cc.pb({-1, -1}); for(int i=1; i<=n; i++){ cin>>a[i]>>b[i]; if(b[i] == -1) b[i] = INF; cc.pb({b[i], a[i]}); } sort(cc.begin(), cc.end()); for(int i=1; i<=n; i++) cost[i] = cc[i].fi, blm[i] = cc[i].se; for(int sp=0; sp<=need; sp++) solve(sp); cout << fixed << setprecision(5) << 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...