Pagini recente » Cod sursa (job #1103066) | Cod sursa (job #2276807) | Cod sursa (job #159470) | Cod sursa (job #544591) | Cod sursa (job #51453)
Cod sursa(job #51453)
#include <stdio.h>
#define in "buline.in"
#define out "buline.out"
#define dim 200001
int A[2*dim], best[2*dim], Nr[2*dim], part[2*dim];
int N;
int main()
{
int a, b;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d", &N);
part[0] = 0;
for ( int i = 1; i <= N; i++ )
{
scanf("%d%d", &a, &b);
if ( b == 1 ) A[i] = a, A[N+i] = a;
else A[i] = -a, A[N+i] = -a;
}
for ( int i = 1; i <= 2*N; i++ ) part[i] = part[i-1] + A[i];
best[1] = A[1];
Nr[1] = 1;
for ( int i = 2; i <= 2*N; i++ )
{
best[i] = A[i];
Nr[i] = i;
if ( best[i] < A[i] + best[i-1] && i - Nr[i-1] < N ) best[i] = A[i] + best[i-1], Nr[i] = Nr[i-1];
}
for ( int i = N+1; i <= 2*N; i++ )
if ( best[i] < part[i] - part[i-N+1] ) best[i] = part[i] - part[i-N+1], Nr[i] = i-N+1;
int maxim = -1000000;
int p;
for ( int i = 1; i <= 2*N; i++ )
{
// printf("%d ", A[i]);
if ( maxim < best[i] ) maxim = best[i], p = i;
}
printf("%d %d %d", maxim, Nr[p], p-Nr[p]+1 );
}