Pagini recente » Cod sursa (job #3180795) | Cod sursa (job #2236450) | Cod sursa (job #2779761) | Cod sursa (job #2962661) | Cod sursa (job #1524812)
#include <fstream>
#include<deque>
#define nmax 400010
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
deque<int>d;
int s,p,l,n;
int v[nmax],sum[nmax];
int main()
{
int i,x,y;
f>>n;
for(i=1;i<=n;++i)
{
f>>x>>y;
if (y==0)
v[i]=v[i+n]=(-1)*x;
else
v[i]=v[i+n]=x;
sum[i]=sum[i-1]+v[i];
}
for (i=n+1;i<=2*n;++i)
sum[i]=sum[i-1]+v[i];
s=-10000;
for (i=1;i<=2*n;++i)
{
while(!d.empty() && sum[i]<=sum[d.back()])
d.pop_back();
d.push_back(i);
if (d.front()==i-n)
d.pop_front();
if (s<sum[i]-sum[d.front()])
{
s=sum[i]-sum[d.front()];
p=d.front()+1;
l=i-d.front();
}
}
g<<s<<" "<<p<<" "<<l;
return 0;
}