Cod sursa(job #51591)

Utilizator cos_minBondane Cosmin cos_min Data 15 aprilie 2007 13:15:26
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>

#define in "buline.in"
#define out "buline.out"
#define dim 200001
#define maxim(a,b) a > b ? a : b

long long a[dim], s[dim], t[dim], k[dim];
long long b[dim], best[dim], nr[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] = b;
        else          a[i] = -b;
    }
    
    // pentru normal
    
    for ( i = 1; i <= n; i++ )
    {
        best[i] = a[i];
        nr[i] = i;
        if ( best[i] < a[i] + best[i-1] ) best[i] = a[i] + best[i-1], nr[i] = nr[i-1];
    }
    
    for ( i = 1; i <= n; i++ )
        if ( smax < best[i] ) smax = best[i], ip = i, is = i-nr[i]+1;
    
    
    // pentru circular
    
    s[1] = a[1];
    t[1] = a[1];
    k[1] = 1;
    
    for ( i = 2; i <= n; i++ )
    {
        s[i] = s[i-1] + a[i];
        t[i] = maxim(t[i-1],s[i]);
        
        if ( t[i-1] >= s[i] ) k[i] = k[i-1];
        else                 k[i] = i;
    }
    
    for ( i = 2; i <= n; i++ )
    {
        if ( smax < t[i-1]+s[n]-s[i-1] )
        {
             smax = t[i-1]+s[n]-s[i-1];
             ip = i;
             if ( k[i] >= i ) is = k[i]-i;
             else             is = (n-i+1)+k[i]; 
        } 
    }
    
    printf("%d %d %d\n",smax,ip,is);
}