Cod sursa(job #1404927)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 28 martie 2015 17:42:17
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<cstdio>
#include<deque>
using namespace std;
int max2(int a,int b){
    if(a>b)
        return a;
    return b;
}
const int N=200000;
deque<int>d;
int v[2*N+1];
int n;
int main(){
    int c1,c2;
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    int s=0,res;
    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];
    }
    d.push_back(1);
    s=res=v[1];
    for(int i=2;i<=2*n;i++){
        s+=v[i];
        d.push_back(i);
        if(i-d.front()==n){
            s-=v[d.front()];
            d.pop_front();
        }
        while(s<v[i]||v[d.front()]<0){
            s-=v[d.front()];
            d.pop_front();
        }
        if(s>res){
            res=s;
            c1=d.front();
            c2=i;
        }
    }
    printf("%d %d %d",res,c1,c2-c1+1);
    return 0;
}