Cod sursa(job #81391)

Utilizator DastasIonescu Vlad Dastas Data 1 septembrie 2007 18:50:00
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>

#define MAX 200001
#define max(a, b) (((a) > (b))?(a):(b))

FILE *in = fopen("buline.in","r"), *out = fopen("buline.out","w");

int n;
int a[MAX << 1];
int s[MAX << 1];

int st = 1, dr = 0;
int dq[MAX];

void read()
{
    fscanf(in, "%d", &n);

    int b = 0;
    for ( int i = 1; i <= n; ++i )
    {
        fscanf(in, "%d %d", &a[i], &b);

        if ( b == 0 )
            a[i] *= -1;
    }

    for ( int i = 1; i < n; ++i )
        a[n+i] = a[i];

    s[1] = a[1];
    for ( int i = 2; i < 2*n - 1; ++i )
        s[i] = s[i-1] + a[i];
}

int main()
{
    read();

    int best = -1000000000;
    int p = 1;
    int l = 1;

    for ( int i = 1; i < 2*n - 1; ++i )
    {
        if ( i - dq[st] > n )
            ++st;
        while ( st <= dr && s[ dq[dr] ] >= s[i] )
            --dr;

        dq[++dr] = i;

        if ( s[i] - s[ dq[st] ] > best )
        {
            best = s[i] - s[ dq[st] ];
            p = dq[st] + 1;
            l = i - p + 1;
        }
    }

    fprintf(out, "%d %d %d\n", best, p, l);

    return 0;
}