Cod sursa(job #27180)

Utilizator cos_minBondane Cosmin cos_min Data 6 martie 2007 10:58:51
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>

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

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

int main()
{
    int b,c;
    int ip, is;
    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[1] = a[1];
    for ( i = 2; i <= 2*n; i++ )
    {
        s[i] = s[i-1] + a[i];
        
        if ( i <= n )
        {
           for ( int j = 2; j < i; j++ )
           {
               if ( smax < s[i]-s[j-1] ) 
               {
                    smax = s[i]-s[j-1];
                    ip = j;
                    is = i-j+1;
               }
               if ( smax == s[i]-s[j-1] && j-i+1 < is-ip )
               {
                    is = i;
                    ip = i-j+1;
               }
           }
        }
        else
        {
           for ( int j = n-2; j < i; j++ )
           {
               if ( smax < s[i]-s[j-1] ) 
               {
                    smax = s[i]-s[j-1];
                    ip = j;
                    is = i-j+1;
               }
               if ( smax == s[i]-s[j-1] && j-i+1 < is-ip )
               {
                    is = i;
                    ip = i-j+1;
               }
           }
        }
    }
    
    printf("%d %d %d\n",smax,ip,is);
}