Cod sursa(job #1408859)

Utilizator raddudjPogonariu Radu raddudj Data 30 martie 2015 11:54:50
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <algorithm>
#include <deque>
#define NMAX 200005

using namespace std;

deque <int> d;
int v[2*NMAX],s[2*NMAX];

void print() {
    for(int i=0; i<d.size(); i++)
        printf("%d ",d[i]);
    printf("\n");
}

int main() {
    int n,x,y,sol=-NMAX,p,q;
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d%d",&x,&y);
        v[i]=x;
        if(!y)
            v[i]*=-1;
        v[n+i]=v[i];
    }
    p=0;
    d.push_front(0);
    for(int i=1; i<=2*n-1; i++) {
        s[i]=s[i-1]+v[i];
        while ( (!d.empty()) && (s[d.back()]>s[i]) ) {
            d.pop_back();
        }
        d.push_back(i);
        if (i-d.front()>n) {
            d.pop_front();
        }
        if (s[d.front()]>0) {
            if (s[i]>sol && i<=n) {
                sol=s[i],p=1,q=i;
                continue;
            }
        }
        if (s[i]-s[d.front()]>sol)
            sol=s[i]-s[d.front()],p=d.front()+1,q=i-d.front();
    }
    printf("%d %d %d",sol,p,q);
}