Submission #843901

#	Time	Username	Problem	Language	Result	Execution time	Memory
843901		oscar1f	Seesaw (JOI22_seesaw)	C++17	100 / 100	56 ms	15700 KiB

seesaw

#include<bits/stdc++.h>
using namespace std;

#define int long long
using ld=long double;

const int MAX_VAL=200*1000+5,INFINI=1000*1000*1000+5;
int nbVal,deb,fin;
int val[MAX_VAL],cumu[MAX_VAL];
vector<pair<ld,ld>> segInter;
vector<pair<ld,ld>> segRep;
ld rep;

ld bary(int debInter,int finInter) {
    return (ld) (cumu[finInter]-cumu[debInter-1])/(finInter-debInter+1);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbVal;
    for (int i=1;i<=nbVal;i++) {
        cin>>val[i];
        cumu[i]=cumu[i-1]+val[i];
    }
    segInter.push_back({-1,bary(1,nbVal)});
    segInter.push_back({bary(1,nbVal),INFINI});
    deb=1;
    fin=nbVal;
    while (deb!=fin) {
        deb++;
        if (bary(deb,fin)>bary(1,nbVal)) {
            deb--;
            fin--;
        }
        //cout<<deb<<" "<<fin<<endl;
        segInter.push_back({bary(deb,fin),bary(deb+1,fin+1)});
    }
    sort(segInter.begin(),segInter.end());
    reverse(segInter.begin(),segInter.end());
    for (auto i:segInter) {
        while (!segRep.empty() and segRep.back().second<i.second) {
            segRep.pop_back();
        }
        segRep.push_back(i);
    }
    reverse(segRep.begin(),segRep.end());
    rep=INFINI;
    for (int i=0;i<(int)segRep.size()-1;i++) {
        rep=min(rep,abs(segRep[i].second-segRep[i+1].first));
    }
    cout<<setprecision(10);
    cout<<rep<<endl;
    return 0;
}

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