Pagini recente » Cod sursa (job #457076) | Cod sursa (job #2124991) | Cod sursa (job #267566) | Clasament baraj_liceu_2014-2019 | Cod sursa (job #754865)
Cod sursa(job #754865)
#include <stdio.h>
#define NMAX 400400
int x[NMAX], S[NMAX], Q[NMAX];
int main()
{
int i, N, cant, cul, p, u, now, best = (1 << 30) * (-1), X1, X2, bestX1 = 1 << 30, bestX2 = 1 << 30;
freopen("buline.in", "r", stdin);
freopen("buline.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++)
{
scanf("%d%d", &cant, &cul);
if (cul)
x[i] = cant;
else
x[i] = cant * (-1);
}
for (i = N + 1; i <= N + N; i++)
x[i] = x[i - N];
for (i = 1; i <= N + N; i++)
S[i] = S[i - 1] + x[i];
p = 1; u = 0;
Q[++ u] = 0;
for (i = 1; i <= N + N; i++)
{
now = S[i] - S[Q[p]];
X1 = Q[p] + 1;
X2 = i - Q[p];
if ((now > best) || (best == now && X1 < bestX1) || (best == now && X1 == bestX1 && X2 < bestX2))
best = now, bestX1 = X1, bestX2 = X2;
while (p <= u && S[i] <= S[Q[u]])
u --;
Q[++ u] = i;
if (Q[p] + N == i)
p ++;
}
printf("%d %d %d", best, bestX1, bestX2);
return 0;
}