Cod sursa(job #1404945)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 28 martie 2015 18:12:48
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<cstdio>
int max2(int a,int b){
    if(a>b)
        return a;
    return b;
}
const int N=200000;
const int INF=10000;

class Deque{
    public:
        int v[2*N+1];
        int l,r;
        Deque(){
            r=0;
            l=1;
        }
        void push_back(int val){
            v[++r]=val;
        }
        void push_front(int val){
            v[--l]=val;
        }
        void pop_front(){
            l++;
        }
        void pop_back(){
            r--;
        }
        bool empty(){
            return l>r;
        }
        int back(){
            return v[r];
        }
        int front(){
            return v[l];
        }
};

int v[2*N+1];
int s[2*N+1];
Deque d;
int n;
int main(){
    int c1,c2;
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    int res=-INF-1;
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d%d",&v[i],&t);
        if(!t)
            v[i]*=-1;
        v[n+i]=v[i];
    }
    for(int i=1;i<=2*n;i++)
        s[i]=s[i-1]+v[i];
    d.push_back(0);
    for(int i=1;i<=2*n;i++){
        if(i==8)
            i=8;
        while(!d.empty()&&s[i]<s[d.back()])
            d.pop_back();
        d.push_back(i);
        if(i-d.front()>n)
            d.pop_front();
        if(s[i]-s[d.front()]>res){
            res=s[i]-s[d.front()];
            c2=i;
            c1=d.front()+1;
        }
    }
    printf("%d %d %d",res,c1,c2-c1+1);
    return 0;
}