Pagini recente » Cod sursa (job #2572583) | Cod sursa (job #1346221) | Cod sursa (job #1750731) | Cod sursa (job #1632080) | Cod sursa (job #488920)
Cod sursa(job #488920)
#include <fstream>
using namespace std;
const char InFile[]="buline.in";
const char OutFile[]="buline.out";
const int MaxN=200005;
ifstream fin(InFile);
ofstream fout(OutFile);
int n,v[MaxN],best[MaxN],st[MaxN],a,sol,start,len,sum;
int main()
{
fin>>n;
best[0]=-1;
st[1]=1;
for(register int i=1;i<=n;++i)
{
fin>>v[i]>>a;
if(a==0)
{
v[i]=-v[i];
}
sum+=v[i];
if(best[i-1]>=0)
{
st[i]=st[i-1];
best[i]=best[i-1]+v[i];
}
else
{
st[i]=i;
best[i]=v[i];
}
}
fin.close();
sol=best[1];
start=1;
len=1;
for(register int i=2;i<=n;++i)
{
if(best[i]>sol)
{
sol=best[i];
start=st[i];
len=i-start+1;
}
}
best[0]=1;
st[1]=1;
for(register int i=1;i<=n;++i)
{
if(best[i-1]<=0)
{
best[i]=best[i-1]+v[i];
st[i]=st[i-1];
}
else
{
best[i]=v[i];
st[i]=i;
}
}
int min=1<<30,minind,minst;
for(register int i=1;i<=n;++i)
{
if(best[i]<min)
{
min=best[i];
minind=i;
}
}
if(sum-min>sol)
{
sol=sum-min;
start=minind+1;
len=n-start+st[minind];
}
fout<<sol<<" "<<start<<" "<<len;
fout.close();
return 0;
}