Pagini recente » Cod sursa (job #1301399) | Cod sursa (job #510158) | Cod sursa (job #2574272) | Cod sursa (job #1649369) | Cod sursa (job #1633909)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
const int NMAX=200005;
int v[NMAX+NMAX],s[NMAX+NMAX];
deque <int> D;
int main()
{
int n,x,y;
f>>n;
for(int i=1;i<=n;i++)
{
f>>x>>y;
if(y==0)
v[i]=v[i+n]=-x;
else
v[i]=v[i+n]=x;
}
for(int i=1;i<=2*n;i++)
s[i]=s[i-1]+v[i];
int sol=0,st=0,lng=0;
D.push_back(1);
for(int i=2;i<=2*n;i++)
{
while(i-n>D.front())
{
D.pop_front();
}
if(s[i]-s[D.front()] > sol)
{
sol=s[i]-s[D.front()];
st=D.front()+1;
lng=i-D.front();
}
while(!D.empty() && s[i]<s[D.back()])
D.pop_back();
D.push_back(i);
}
g<<sol<<" "<<st<<" "<<lng<<"\n";
return 0;
}