Pagini recente » Cod sursa (job #2980238) | Cod sursa (job #1476919) | Cod sursa (job #1081731) | Cod sursa (job #2548698) | Cod sursa (job #2279696)
#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)%n;
if(p1==0)
p1=n;
}
}
}
g<<maxi<<' '<<p1<<' '<<l;
return 0;
}