Pagini recente » Cod sursa (job #176153) | Cod sursa (job #2669210) | Cod sursa (job #1369843) | Cod sursa (job #2130249) | Cod sursa (job #2201391)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int i,l,p,p1,u,dq[400001],v[400001],a,n,maxi;
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;
}