Cod sursa(job #26825)

Utilizator cos_minBondane Cosmin cos_min Data 5 martie 2007 21:45:01
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>

#define in "buline.in"
#define out "buline.out"
#define dim 400001

int a[dim];
int n, smax, i, j, s;

int main()
{
    int b,c;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d",&n);
    for ( i = 1; i <= n; i++ )
    { 
        scanf("%d%d",&b,&c); 
        if ( c == 1 ) a[i+n] = a[i] = b;
        else          a[i+n] = a[i] = -b;
    }
    
    s = 0;
    smax = 0;
    int i1 = 1;
    i = 1;
    j = 1;
    for ( int k = 1; k <= 2*n; k++ )
    {
        if ( s+a[k] > smax )
        {
             if ( k - i1 == n )
             {
                  i1 += 1;
             }
             else
             {
                 smax = s + a[k];
                 s += a[k];
                 i = i1;
                 j = k;
             }
        }
        else if ( s+a[k] > 0 ) 
        {
             if ( k - i1 == n )
             {
                  i1 += 1;
             }
             else s += a[k];
        }
        else
        {
            s = 0;
            i1 = k+1;
        }  
        //printf("%d %d\n", s, j);
    }
    
    printf("%d %d %d",smax,i,j-i+1);
}