oj.uz

Submission #199802

# Submission time Handle Problem Language Result Execution time Memory
199802 2020-02-03T13:08:45 Z path Pismo (COCI18_pismo) C++14
70 / 70
 122 ms 808 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define f first
#define s second
#define pb push_back
const int N=1e5+5;
int n,a[N],mn,ans;
bool chk(int x){
    priority_queue< pair<int,int> > q[2];
    q[0].push({-a[0],0}); q[1].push({a[0],0});
    q[0].push({-a[1],1}); q[1].push({a[1],1});
    if(q[1].top().f+q[0].top().f<=x)
        return 1;
    int st=0;
    for(int i=2; i< n; i++){
        while((q[0].top()).s<st ) q[0].pop();
        while((q[1].top()).s<st ) q[1].pop();
        q[0].push({-a[i],i}); q[1].push({a[i],i});
        if((q[1].top()).f+(q[0].top()).f<=x)
            return 1;
        while(q[1].size()&&q[1].top().f+q[0].top().f>x){
            st=min(q[1].top().s,q[0].top().s)+1;
            while((q[0].top()).s<st ) q[0].pop();
            while((q[1].top()).s<st ) q[1].pop();
        }
        if(st<i)
            return 1;
    }
    return 0;
}
int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int s=0,e=1e9,mid;
    while(s<=e){
        mid=(s+e)/2;
        if(chk(mid))
            e=mid-1;
        else
            s=mid+1;
    }
    cout<<e+1<<'\n';
    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 8 ms 376 KB Output is correct
5 Correct 68 ms 632 KB Output is correct
6 Correct 91 ms 632 KB Output is correct
7 Correct 122 ms 808 KB Output is correct