Submission #1288528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288528		Math4Life2020	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	742 ms	492 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ld = long double; using pld = pair<ld,ld>;
const ll INF = 1e18;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    cout << setprecision(20);
    ll N,K; cin >> N >> K;
    vector<pii> vba;
    for (ll i=0;i<N;i++) {
        ll a,b; cin >> a >> b;
        if (b==-1) {
            b=INF;
        }
        vba.push_back({b,a});
    }
    sort(vba.begin(),vba.end());
    ll A[N]; ll B[N];
    for (ll i=0;i<N;i++) {
        B[i]=vba[i].first;
        A[i]=vba[i].second;
    }
    ll psf[N+1]; //prefix sum for finals: first block of length L (=idx)
    //-> take bottom K-L values of remaining N-L
    multiset<ll> rnum;
    psf[N]=0;
    for (ll i=K;i<N;i++) {
        rnum.insert(A[i]);
        psf[i]=0;
    }
    for (ll i=(K-1);i>=0;i--) {
        rnum.insert(A[i]);
        ll v = *(rnum.begin()); rnum.erase(rnum.begin());
        psf[i]=psf[i+1]+v;
    }
    ld ans = psf[0];
    for (ll bf=0;bf<=K;bf++) {
        vector<ld> dp0(N+1,INF); //bcurr -> minvalue
        dp0[0]=0;
        for (ll i=0;i<K;i++) {
            vector<ld> dp1(N+1,INF);
            for (ll bc=0;bc<bf;bc++) { //if bc=bf already you could just use the global feature (on prev turn)
                if (dp0[bc]<INF) {
                    //take A
                    dp1[bc]=min(dp1[bc],dp0[bc]+((ld)A[i])/((ld)(bf+1)));
                    //take B
                    if (B[i]!=INF) {
                        dp1[bc+1]=min(dp1[bc+1],dp0[bc]+((ld)(B[i]))/((ld)(bc+1)));
                    }
                }
            }
            dp0=dp1;
            //now consider bc=bf term: ready to fly out
            ans = min(ans,dp0[bf]+((ld)psf[i+1])/((ld)(bf+1)));
        }
    }
    cout << ans << "\n";
}

• 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