Pagini recente » Cod sursa (job #1301151) | Cod sursa (job #734597) | Cod sursa (job #1754887) | Cod sursa (job #481587) | Cod sursa (job #86866)
Cod sursa(job #86866)
#include <stdio.h>
int N, V[400200], S[400200], DQ[400200], P[400200];
int main()
{
int i, n, lo, hi, smax, p, l, s, pp;
freopen("buline.in", "r", stdin);
scanf("%d",&N);
for (i = 1; i <= N; i++){scanf("%d%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 (DQ[0] = 666000666, i = hi = 1, smax = p = l = lo = 0; i <= n; i++)
{
while (i-P[lo]>=N && lo<hi) lo++;
if (lo==hi) break;
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;}
}
for (i = 1; i <= N; i++)
if (smax<V[i]) smax = V[i], p = i, l = 1;
freopen("buline.out", "w", stdout);
printf("%d %d %d\n", smax, p, l);
return 0;
}