Cod sursa(job #185779)

Utilizator tm_raduToma Radu tm_radu Data 26 aprilie 2008 00:15:24
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>
#define NM 200002

int n, i, j, k, h;
int s[NM];
int a[NM], pos[NM];
int p, u, smax, stot, smin;
int pmin, umin;

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]),
		stot += a[i];
	p = u = 1, smax = a[1];
	for ( i = 1; i <= 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] ) smax = s[i], p = pos[i], u = i-pos[i]+1;
	}
	for ( i = 1; i <= n; a[i] = -a[i], i++ );
	for ( i = 1; i <= 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 ( smin < s[i] ) smin = s[i], pmin = pos[i], umin = i;
	}
    smin = -smin;
	if ( stot - smin > smax ) smax = stot-smin, p = umin%n+1, u = n-umin+pmin-1;
    printf("%d %d %d\n", smax, p, u);
    
    return 0;
}