Pagini recente » Cod sursa (job #3194871) | Cod sursa (job #1921512) | Cod sursa (job #816899) | Cod sursa (job #1924155) | Cod sursa (job #2201395)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int i,l,p,p1,u,dq[400001],a,n,maxi;
long long v[400001];
int main()
{ f>>n;
for(i=1;i<=n;i++){
f>>v[i]>>a;
if(a==0)
v[i]=-v[i];
v[i+n]=v[i];
v[i]=v[i-1]+v[i];
}
for(i=n+1;i<=2*n;i++)
v[i]=v[i-1]+v[i];
p=0;u=0;
for(i=1;i<=2*n;i++){
while(p<=u&&v[i]<v[dq[u]])
u--;
dq[++u]=i;
if(i-dq[p]>=n)
p++;
if(i-dq[p]<n){
if(maxi<v[i]-v[dq[p]]){
maxi=v[i]-v[dq[p]];
l=i-dq[p];
p1=dq[p+1];
}
}
}
g<<maxi<<' '<<p1<<' '<<l;
return 0;
}