Submission #199802

#	Time	Username	Problem	Language	Result	Execution time	Memory
199802		path	Pismo (COCI18_pismo)	C++14	70 / 70	122 ms	808 KiB

pismo

#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 / 70