Submission #593566

#TimeUsernameProblemLanguageResultExecution timeMemory
593566oleh1421Let's Win the Election (JOI22_ho_t3)C++17
56 / 100
2576 ms8364 KiB
//#pragma GCC optimize("O3") //#pragma GCC target("avx2") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> //#define y2 y_2 #define endl '\n' using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; const ll inf=1e18; mt19937 rnd(time(NULL)); const ll mod=998244353; const int N=510; const int Lg=16; ld pref[N][N]; ld suf[N][N]; void solve(){ int n,k;cin>>n>>k; vector<pair<ll,ll> >v; for (int i=1;i<=n;i++){ ll a,b;cin>>a>>b; if (b==-1) b=inf; v.push_back({b,a}); } sort(v.begin(),v.end()); ld res=inf; for (int l=0;l<k;l++){ for (int i=0;i<=n+1;i++){ for (int j=0;j<=n+1;j++){ pref[i][j]=suf[i][j]=inf; } } pref[0][0]=0.0; for (int i=0;i<n;i++){ for (int j=0;j<=i;j++){ pref[i+1][j]=min(pref[i+1][j],pref[i][j]+(ld)v[i].second/(l+1.0)); if (v[i].first<inf) pref[i+1][j+1]=min(pref[i+1][j+1],pref[i][j]+(ld)v[i].first/(j+1.0)); } } vector<ll>u; for (int i=n-1;i>=0;i--){ ld cur=pref[i+1][l]; for (int j=0;j<k-i-1;j++) cur+=(ld)u[j]/(l+1.0); res=min(res,cur); // cout<<l<<" "<<i+1<<" "<<cur<<" "<<v[i].second<<endl; u.push_back(v[i].second); sort(u.begin(),u.end()); } ld cur=0.0; for (int i=0;i<k;i++) cur+=u[i]; res=min(res,cur); } cout<<setprecision(10)<<fixed<<res<<endl; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int tt=1; // cin>>tt; while (tt--){ solve(); } return 0; } /** 3 5 2 7 3 1 6 8 4 **/
#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...