Pagini recente » Cod sursa (job #2488574) | Profil BGeorgiana | Cod sursa (job #2423748) | Monitorul de evaluare | Cod sursa (job #1702911)
#include <iostream>
#include<fstream>
#include<deque>
using namespace std;
deque<int> d;
int sum[400005],i,n,x,summax,p,l;
bool semn;
int main()
{
ifstream f("buline.in");
ofstream g("buline.out");
f>>n;
for(i=1;i<=n;i++)
{f>>x>>semn;
if(semn)sum[i]=sum[i-1]+x;
else sum[i]=sum[i-1]-x;
}
for(i=1;i<=n;i++)
{
sum[n+i]=sum[i]+sum[n];
}
for(i=1;i<=2*n;i++)
{
if(!d.empty()&&i-d.front()>=n) d.pop_front();
while(!d.empty()&&sum[i]<sum[d.back()])
d.pop_back();
d.push_back(i);
if(sum[i]>summax&&i<=n) {summax=sum[i];l=i;p=1;}
if(sum[i]-sum[d.front()]>summax)
{summax=sum[i]-sum[d.front()];p=d.front()+1;l=i-d.front();}
}
g<<summax<<' '<<p<<' '<<l;
return 0;
}