Pagini recente » Cod sursa (job #697695) | Cod sursa (job #2359908) | Cod sursa (job #2202699) | Cod sursa (job #1196027) | Cod sursa (job #1357199)
#include <cstdio>
using namespace std;
#define Nmax 200002
FILE *f = fopen ( "buline.in", "r" );
FILE *g = fopen ( "buline.out", "w" );
int v[Nmax];
int sum[Nmax], smax[Nmax], idx[Nmax];
int main(){
int N, s = 0, st, x, sol = 0, poz, lg;
fscanf ( f, "%d ", &N );
for ( int i = 1; i <= N; ++i ){
fscanf ( f, "%d%d", &v[i], &x );
if ( x == 0 )
v[i] = -v[i];
}
for ( int i = 1; i <= N; ++i )
sum[i] = sum[i-1] + v[i];
for ( int i = 1; i <= N; ++i )
if ( smax[i-1] > sum[i] ){
smax[i] = smax[i-1];
idx[i] = idx[i-1];
}
else {
smax[i] = sum[i];
idx[i] = i;
}
for ( int i = 1; i <= N; ++i ){
if ( s <= 0){
s = 0;
st = i;
}
s += v[i];
if ( s > sol ) {
sol = s;
poz = st;
lg = i - st + 1;
}
}
for ( int i = 1; i <= N; ++i )
if ( sum[N] - sum[i-1] + smax[i-1] > sol ){
sol = sum[N] - sum[i-1] + smax[i-1];
poz = i;
lg = N + idx[i-1] - i + 1;
}
fprintf ( g, "%d %d %d", sol, poz, lg );
return 0;
}