Pagini recente » Clasament cerculdeinfo-lectia9-cuplaj_flux | Cod sursa (job #1965004) | Cod sursa (job #1871537) | Cod sursa (job #915859) | Cod sursa (job #2183194)
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#define val first
#define pos second
/// TONI BO$$ was here
/// #MLC
using namespace std;
int v[200001];
pair<int,int> smin[200001],smax[200001];
int main()
{
int n,s,i,c,rez,p,l;
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n);
s=0;
for(i=1; i<=n; i++)
{
scanf("%d%d",&v[i],&c);
if(c==0)
v[i]=-v[i];
s+=v[i];
}
smin[1]=smax[1]={v[1],1};
for(i=2; i<=n; i++)
{
if(smin[i-1].val>0)
smin[i]={v[i],i};
else
smin[i]={smin[i-1].val+v[i],smin[i-1].pos};
if(smax[i-1].val<0)
smax[i]={v[i],i};
else
smax[i]={smax[i-1].val+v[i],smax[i-1].pos};
}
rez=v[1];
p=1;
l=1;
for(i=1; i<=n; i++)
{
if(s-smin[i].val>rez)
{
rez=s-smin[i].val;
p=i+1;
l=n-(i-smin[i].pos+1);
}
else
if(s-smin[i].val==rez && p>i+1)
{
p=i+1;
l=n-(i-smin[i].pos+1);
}
else
if(s-smin[i].val==rez && p==smin[i].pos && l>n-(i-smin[i].pos+1))
l=n-(i-smin[i].pos+1);
if(smax[i].val>rez)
{
rez=smax[i].val;
p=smax[i].pos;
l=i-p+1;
}
else
if(smax[i].val==rez && p>smax[i].pos)
{
p=smax[i].pos;
l=i-p+1;
}
else
if(smax[i].val==rez && p==smax[i].pos && l>i-p+1)
l=i-p+1;
}
printf("%d %d %d",rez,p,l);
return 0;
}