Pagini recente » Cod sursa (job #2236488) | Cod sursa (job #2031165) | Cod sursa (job #63575) | Cod sursa (job #2247821) | Cod sursa (job #2118402)
#include <fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
/*int v[200001],n,i,k,s,l,p,smax,l1,p1,smin,l2,p2,l3,p3,s2,S;
int main()
{
f>>n;
smax=-10001;
s=-1;
for(i=1;i<=n;i++)
{
f>>v[i]>>k;
v[i]+=2*(k-1)*v[i];
S+=v[i];
if(s>=0)
{
s+=v[i];
l++;
}
else
{
p=i;
s=v[i];
l=1;
}
if(smax<s)
{
smax=s;
p1=p;
l1=l;
}
if(s2<0)
{
s2+=v[i];
l2++;
}
else
{
p2=i;
s2=v[i];
l2=1;
}
if(smin>s2)
{
smin=s2;
p3=p2;
l3=l2;
}
}
if(smax<S-smin)
{
smax=S-smin;
p1=p3+l3;
l1=n-l3;
}
g<<smax<<" "<<p1<<" "<<l1;
return 0;
}*/
int n,dr,st,i,k,Max,p,l,v[400001],s[400001];
int main(){
f>>n;
dr=1;st=1;Max=-10001;
for(i=1;i<=n;i++){
f>>s[i]>>k;
s[i]+=2*s[i]*(k-1)+s[i-1];
while(dr>=1&&s[i]<=s[v[dr]])
dr--;
dr++;
v[dr]=i;
if(Max<s[i]-s[v[1]]){
Max=s[i]-s[v[1]];
p=v[st]+1;
l=i-p+1;
}
s[i+n]=s[i];
}
for(i=n+1;i<=2*n;i++){
s[i]+=s[n];
while(st<=dr&&s[i]<=s[v[dr]])
dr--;
dr++;
v[dr]=i;
if(v[st]==i-n-1)
st++;
if(Max<s[i]-s[v[st]]){
Max=s[i]-s[v[st]];
p=(v[st]+1)%n;
l=i-v[st];
}
}
g<<Max<<" "<<p<<" "<<l;
}