Pagini recente » Cod sursa (job #268297) | Cod sursa (job #343402) | Cod sursa (job #2200904) | Cod sursa (job #2258421) | Cod sursa (job #26961)
Cod sursa(job #26961)
//100p
#include <stdio.h>
#define MAX(a, b) ( (a) < (b) ? (b) : (a) )
#define NMAX 400001
#define INF 2000001
long long S[NMAX], St[NMAX], max;
int Poz[NMAX];
int i, j, N, NN, nr, cul;
int s1, s2, pmax, lmax;
void add(long long e, int pz)
{
while (s2 >= s1 && St[s2] > e) s2--;
s2++;
St[s2] = e;
Poz[s2] = pz;
if (pz - Poz[s1] + 1 > N) s1++;
}
int main()
{
freopen("buline.in", "r", stdin);
freopen("buline.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++)
{
scanf("%d %d", &nr, &cul);
if (cul == 0) nr = -nr;
S[i] = S[i - 1] + nr;
}
NN = N;
for (i = 1; i < N; i++)
S[++NN] = S[i] + S[N];
s1 = s2 = 0;
max = -INF;
for (i = 1; i < NN; i++)
{
if (max < S[i] - St[s1])
{
max = (long long)S[i] - St[s1];
pmax = Poz[s1] + 1;
lmax = i - pmax + 1;
}
add(S[i], i);
}
printf("%lld ", max);
printf("%d %d\n", pmax, lmax);
return 0;
}