Submission #1175065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175065		Math4Life2020	Seesaw (JOI22_seesaw)	C++20	100 / 100	96 ms	19016 KiB

seesaw

#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>;

ll N; const ll Nm = 2e5+5; const ld INF = 1e18; const ld DEL = 1e-10;
ld avg;
ld psa[Nm+1];
ld ans = INF;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    psa[0]=0.0L;
    for (ll i=0;i<N;i++) {
        ll a1; cin >> a1;
        psa[i+1]=psa[i]+a1;
    }
    avg = psa[N]/N;
    //cout << "avg="<<avg<<"\n";
    ld maxv = avg;
    set<pld> s0;
    ld imin = avg;
    s0.insert({avg,avg});
    for (ll L=1;L<N;L++) {
        ll xmin = 0; 
        ll xmax = N-L;
        while (xmin != xmax) {
            ll xt = (xmin+xmax+1)/2;
            ld avt = (psa[xt+L]-psa[xt])/L;
            if (avt >= (avg+DEL)) {
                xmax = xt-1;
            } else {
                xmin = xt;
            }
        }
        s0.insert({(psa[xmin+L]-psa[xmin])/L,(psa[xmin+1+L]-psa[xmin+1])/L});
        //cout << "pair: "<<(psa[xmin+L]-psa[xmin])/L<<","<<(psa[xmin+1+L]-psa[xmin+1])/L<<"\n";
        imin = min(imin,(psa[xmin+L]-psa[xmin])/L);
    }
    ans = min(ans,avg-imin);
    while (s0.size()>=2) {
        auto A0 = s0.begin(); pld p0 = *A0;
        s0.erase(A0);
        maxv = max(maxv,p0.second);
        ld cmin = (*(s0.begin())).first;
        //cout << "maxv,cmin="<<maxv<<","<<cmin<<"\n";
        ans = min(ans,maxv-cmin);
    }
    cout << setprecision(20);
    cout << ans << "\n";
}

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33