Pagini recente » Cod sursa (job #1497618) | Cod sursa (job #2619648) | Cod sursa (job #1689454) | Cod sursa (job #2628390) | Cod sursa (job #1694528)
#include<fstream>
#include<deque>
#include<vector>
#include <cstring>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,m,k,i,j,p,x,y,a[400005],t,sol=-2000000000,poz1,poz2;
deque<int> d;
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>x>>y;
if(y==0) x=-x;
a[i]=a[i+n]=x;
}
for(i=1;i<=2*n;i++)
{
a[i]=a[i]+a[i-1];
}
for(i=1;i<=2*n;i++)
{
while(!d.empty() && a[d.back()]>=a[i]){
d.pop_back();
}
d.push_back(i);
if(d.front()==i-n)
d.pop_front();
if(sol < (a[i]-a[d.front()]) )
{
sol=a[i]-a[d.front()];
poz1=d.front()+1;
poz2=i-d.front();
}
//fout<<a[i]<<" "<<a[d.front()]<<"\n";
}
fout<<sol<<" "<<poz1<<" "<<poz2<<"\n";
for(i=1;i<=2*n;i++)
{
//fout<<a[i]<<" ";
}
}