Pagini recente » Cod sursa (job #838227) | Cod sursa (job #839665) | Cod sursa (job #2282018) | Cod sursa (job #1672847) | Cod sursa (job #935644)
Cod sursa(job #935644)
#include <stdio.h>
#define MAXN 400005
int N, x[MAXN], s[MAXN], bst[MAXN], bstp[MAXN];
int d[MAXN], p[MAXN], dl, dr;
void initdeque()
{
dl = 0; dr = -1;
}
void adddeque( int val, int poz, int L )
{
for (; dr >= dl && d[dr] >= val; dr--);
d[ ++dr ] = val;
p[ dr ] = poz;
if (poz - p[dl] >= L)
dl++;
}
int main()
{
freopen("buline.in", "rt", stdin);
freopen("buline.out", "wt", stdout);
scanf("%d", &N);
for (int i = 1; i <= N; i++)
{
int val, t;
scanf("%d %d", &val, &t);
if (t == 0)
x[i] = -val;
else
x[i] = val;
s[i] = s[i - 1] + x[i];
}
for (int i = N + 1; i < N + N; i++)
x[i] = x[i - N],
s[i] = s[i - 1] + x[i];
initdeque();
adddeque( s[0], 0, N );
int MAX = -0x3f3f3f3f, MAXi = -1;
for (int i = 1; i < N + N; i++)
{
bst[i] = s[i] - d[dl];
bstp[i] = p[dl];
adddeque( s[i], i, N );
if (bst[i] > MAX)
{
MAX = bst[i];
MAXi = i;
}
}
printf("%d %d %d\n", MAX, bstp[MAXi] + 1, MAXi - bstp[MAXi]);
return 0;
}