Pagini recente » Cod sursa (job #1872657) | Cod sursa (job #1154588) | Cod sursa (job #1015615) | Cod sursa (job #123170) | Cod sursa (job #1802369)
#include <cstdio>
using namespace std;
int v[200001],w[200001];
int main()
{
FILE *fin=fopen ("buline.in","r");
FILE *fout=fopen ("buline.out","w");
int n,maxs,p,l,sum,i,pi,aux,x,semn;
fscanf (fin,"%d",&n);
maxs=p=l=-2000000000;
sum=0;
for (i=1;i<=n;i++){
fscanf (fin,"%d%d",&x,&semn);
if (!semn)
v[i]=-x;
else v[i]=x;
sum+=v[i];
}
pi=1;
for (i=1;i<=n;i++){
if (w[i-1]+v[i]>v[i])
w[i]=w[i-1]+v[i];
else {
w[i]=v[i];
pi=i;
}
if (maxs<w[i]){
maxs=w[i];
p=pi;
l=i-pi+1;
}
else if (maxs==w[i]){
if (pi<p){
p=pi;
l=i-pi+1;
}
else if (p==pi && l>i-pi+1)
l=i-pi+1;
}
}
pi=1;
for (i=1;i<=n;i++){
if (w[i-1]+v[i]<v[i])
w[i]=w[i-1]+v[i];
else {
w[i]=v[i];
pi=i;
}
if (maxs<sum-w[i]){
maxs=sum-w[i];
p=(i+1)%n;
if (!p)
p=n;
l=n-(i-pi+1);
}
else if (maxs==sum-w[i]){
aux=(i+1%n);
if (!aux)
aux=n;
if (aux<p){
p=aux;
l=n-(i-pi+1);
}
else if (p==aux && l>i-pi+1)
l=n-(i-pi+1);
}
}
fprintf (fout,"%d %d %d",maxs,p,l);
return 0;
}