Pagini recente » Cod sursa (job #1908905) | Cod sursa (job #3277742) | Cod sursa (job #2923371) | Cod sursa (job #1241474) | Cod sursa (job #3165698)
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int v[200001], ss[200301];
int main()
{
int n, s=0, t, smin=0, first, last, firstin, lastin, i1, i2, x, i, sinit=0;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>v[i]>>t;
if(t==0)
{
v[i]=-v[i];
}
sinit+=v[i];
}
s=0;
ss[1]=v[1];
i1=i2=1;
for(i=2;i<=n;i++)
{
if(ss[i-1]+v[i]>=v[i])
{
ss[i]=ss[i-1]+v[i];
i2=i;
}
else
{
ss[i]=v[i];
i1=i2=i;
}
if(s<ss[i])
{
s=ss[i];
first=i1;
last=i2;
}
}
smin=INT_MAX;
ss[1]=v[1];
i1=i2=1;
for(i=2;i<=n;i++)
{
if(ss[i-1]+v[i]<=v[i])
{
ss[i]=ss[i-1]+v[i];
i2=i;
}
else
{
ss[i]=v[i];
i1=i2=i;
}
if(smin>ss[i])
{
smin=ss[i];
firstin=i1;
lastin=i2;
}
}
smin=sinit-smin;
if(s>=smin)
{
fout<<s<<" "<<first<<" "<<last-first+1;
}
else
{
fout<<smin<<" "<<lastin+1<<" "<<n-lastin+firstin-1;
}
}