Pagini recente » Cod sursa (job #1738071) | Cod sursa (job #1255781) | Cod sursa (job #2102927) | Cod sursa (job #2987628) | Cod sursa (job #27155)
Cod sursa(job #27155)
#include <stdio.h>
#define in "buline.in"
#define out "buline.out"
#define NMAX 400001
int a[NMAX];
int n, smax;
int best[NMAX];
int main()
{
freopen( in, "r", stdin );
freopen( out, "w", stdout );
scanf( "%d", &n );
int i, col;
for ( i = 1; i <= n; ++i )
{
scanf( "%d%d", &a[i], &col );
if ( col == 0 ) a[i] *= -1;
}
//for ( i = 1; i <= n; printf( "%d ", a[i++] ) );
for ( i = 1; i <= n - 1; ++i )
{
a[i+n] = a[i];
}
//for ( i = 1; i <= 2*n-1; printf( "%d ", a[i++] ) );
/*
best[0] = 0;
smax = 0;
int st = 1, dr = 1;
for ( i = 1; i <= 2*n-1; ++i )
{
best[i] = a[i];
if ( best[i] < best[i-1] + a[i] )
best[i] = best[i-1] + a[i];
if ( best[i] > smax )
smax = best[i];
}
printf( "%d %d %d\n", smax, st, dr );
*/
int s = 0; smax = 0;
int i1 = 1, k, j;
for ( k = 1; k <= 2*n-1; k++ )
if ( a[k] + s > smax )
{
s += a[k];
smax = s;
i = i1; // actualizez inceputul secventei
j = k; // sfarsitul ei
}
else
if ( a[k] + s > 0 ) // numerele negative se iau in secventa
s += a[k]; // numai daca suma ei nu devine 0 sau < 0
else
{
s = 0; // caut o noua secventa
i1 = k + 1; // de la aceasta pozitie
}
printf( "%d %d %d\n", smax, i, j - i + 1 );
return 0;
}