Pagini recente » Cod sursa (job #460361) | Cod sursa (job #463511) | Cod sursa (job #651820) | Cod sursa (job #119662) | Cod sursa (job #462554)
Cod sursa(job #462554)
#include <cstdio>
const char FIN[] = "buline.in", FOU[] = "buline.out";
const int MAX = 200006;
short V[MAX];
int Suma[MAX], best[MAX] = { 0 , 1 } ;
int N, S, P, L ;
int main ()
{
freopen ( FIN, "r", stdin ) ;
freopen ( FOU, "w", stdout ) ;
scanf("%d", &N);
for (int i = 1, nr = 0, cul = 0; i <= N; ++i)
{
scanf ( "%d %d", &nr, &cul ) ;
Suma[ i ] = Suma[ i - 1 ] + ( V[ i ] = cul ? nr : -nr ) ;
}
int S = V[N], P = N, L = 1;
for (int i = N - 1, s = V[N], p = N; i ; --i)
{
( s += V[ i ] ) <= V[ i ] ? s = V[ i ], p = i : 0 ;
S <= s ? S = s, P = i, L = p - i + 1 : 0;
}
for (int i = 2; i <= N; ++i)
Suma[ best[ i - 1 ] ] < Suma[ i ] ? best[ i ] = i : best[ i ] = best[ i - 1 ] ;
for (int s = 0, i = N, p = 0; i ; --i)
S < ( p = ( s += V[ i ] ) + Suma[ best[ i - 1 ] ] ) || ( S == p && P > i ) ? S = p, P = i, L = N - i + 1 + best[ i - 1 ] : 0 ;
printf("%d %d %d", S, P, L);
return 0;
}