Pagini recente » Rating Andrei Calota (andreic06) | Profil 6claudiae5291wh0 | Istoria paginii template/abc | Istoria paginii utilizator/8claudiac4991wl0 | Cod sursa (job #86892)
Cod sursa(job #86892)
#include <stdio.h>
#define INF 666000666
int N;
long long V[400200], S[400200], DQ[400200], P[400200];
int main()
{
int i, n, lo, hi, p, l, pp;
long long smax=-INF, s;
freopen("buline.in", "r", stdin);
scanf("%d",&N);
for (i = 1; i <= N; i++){scanf("%lld%d", V+i, &p);
if(!p) V[i] = -V[i]; }
for (i = 1; i <= N; i++) V[i+N] = V[i];
for (i = 1, n = 2*N; i <= n; i++) S[i] = S[i-1]+V[i];
for (i = 1; i <= N; i++) {
if (smax<V[i]) smax = V[i], p = i, l = 1;
if (smax<S[i]) smax = S[i], p = 1, l = i; }
for (DQ[0] = INF, i = hi = 1, lo = 0; i <= n; i++)
{
while (i-P[lo]>=N && lo<hi) lo++;
while (DQ[hi-1]>S[i] && hi>lo) hi--;
DQ[hi] = S[i]; P[hi++] = i; s = S[i]-DQ[lo]; pp = P[lo]+1;
if (smax<s) smax = s, p = pp, l = i-pp+1;
else{if (smax==(S[i]-DQ[lo]))
if ((p>pp)||((p==pp)&&(l>(i-pp+1)))) p = pp, l = i-pp+1;}
}
freopen("buline.out", "w", stdout);
printf("%lld %d %d\n", smax, p, l);
return 0;
}