oj.uz

답안 #843901

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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