Cod sursa(job #185770)

Utilizator tm_raduToma Radu tm_radu Data 25 aprilie 2008 23:59:34
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#define NM 400002

int n, i, j, k, h;
long long int s[NM];
int a[NM], pos[NM];
int p, u, smax, st, dr, stot;

int main()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    scanf("%d", &n);
    for ( i = 1; i <= n; i++ )
        scanf("%d %d", &a[i], &j),
        a[i] = (j == 0 ? -a[i] : a[i]),
        a[i+n] = a[i],
        stot += a[i];
    p = u = 1, smax = a[1];
    pos[1] = 1;
    for ( i = 1; i <= 2*n; i++ )
    {
        if ( s[i-1] <= 0 ) s[i] = a[i], pos[i] = i;
        else               s[i] = s[i-1] + a[i], pos[i] = pos[i-1];
        if ( smax < s[i] && i-pos[i]+1 <= n ) smax = s[i], p = (pos[i]-1)%n+1, u = i-pos[i]+1;
        if ( i >= n && smax < s[i] - s[i-n] ) smax = s[i] - s[i-n], p = (i-n)%n+1, u = n;
    }    
    if ( p == 2*n ) smax = stot, p = 1, u = n;
    printf("%d %d %d\n", smax, p, u);
    
    return 0;
}