Submission #593570

#	Time	Username	Problem	Language	Result	Execution time	Memory
593570		oleh1421	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	2210 ms	8396 KiB

Main

//#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];
ll sum[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=0;
    vector<ll>u;
    for (int i=n-1;i>=0;i--){
        sum[i]=0;
        for (int j=0;j<k-i-1;j++) sum[i]+=u[j];
        u.push_back(v[i].second);
        sort(u.begin(),u.end());
    }
    for (int i=0;i<k;i++) res+=u[i];
    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));
            }
        }
        for (int i=n-1;i>=0;i--){
            ld cur=pref[i+1][l];
            cur+=(ld)sum[i]/(l+1.0);
            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
**/

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23