oj.uz

Submission #843901

# Submission time Handle Problem Language Result Execution time Memory
843901 2023-09-04T16:44:49 Z oscar1f Seesaw (JOI22_seesaw) C++17
100 / 100
 56 ms 15700 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2596 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2596 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2596 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 54 ms 14024 KB Output is correct
13 Correct 56 ms 15568 KB Output is correct
14 Correct 55 ms 15700 KB Output is correct
15 Correct 55 ms 14280 KB Output is correct
16 Correct 54 ms 14800 KB Output is correct