Pagini recente » Cod sursa (job #943357) | Cod sursa (job #2188667) | Cod sursa (job #2577594) | Cod sursa (job #1075815) | Cod sursa (job #1558895)
# include <iostream>
# include <fstream>
# include <limits.h>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n, v[200010], sum[400020], deq[400020];
int main()
{
int suma, Smaxi, mini, p, l, ramas, i, color, prim, ulti;
suma=mini=ramas=0;
Smaxi=-INT_MAX;
f>>n;
for (i=1; i<=n; i++)
{
f>>v[i]>>color;
if (color==0)
v[i]=-v[i];
v[n+i]=v[i];
sum[i]=sum[i-1]+v[i];
}
for (i=n+1; i<=2*n; i++)
sum[i]=sum[i-1]+v[i];
prim=1;
ulti=0;
for (i=1; i<=2*n; i++)
{
while (sum[i]<=sum[deq[ulti]] && prim<=ulti)
{
ulti--;
}
deq[++ulti]=i;
if (deq[prim]==i-n) // dapasesc lungimea
prim++;
if (Smaxi<sum[i]-sum[deq[prim]])
{
Smaxi=sum[i]-sum[deq[prim]];
p=deq[prim]+1;
l=i-deq[prim];
}
}
g<<Smaxi<<' '<<p<<' '<<l;
return 0;
}