Pagini recente » Cod sursa (job #3300077) | Cod sursa (job #3296156) | Cod sursa (job #1607204) | Cod sursa (job #458334) | Cod sursa (job #130983)
Cod sursa(job #130983)
#include <fstream.h>
ifstream fin ("buline.in");
ofstream fout("buline.out");
int a[200010],poz,lung,n;
long Smax=0,P;
void citire()
{
fin>>n;
short k;
for (int i=1;i<=n;i++)
{
fin>>a[i]>>k;
if (k==0)
a[i]=-a[i];
}
fin.close();
}
void parc()
{
long S=0,incl=0;
poz=0;
lung=0;
for (int i=1;i<=n;i++)
{
P+=a[i];
S+=a[i];
if (S<0)
{
S=0;
incl=i+1;
}
else
if (S>Smax)
{
Smax=S;
poz=incl;
lung=i-incl+1;
}
}
for (int ii=1;ii<=n;ii++)
a[ii]=-a[ii];
S=0;
incl=0;
int poz1=0,lung1=0,Smin=-10214;
for (int k=1;k<=n;k++)
{
S+=a[k];
if (S<0)
{
S=0;
incl=k+1;
}
else
if (S>Smin)
{
Smin=S;
poz1=incl;
lung1=k-incl+1;
}
}
if (P+Smin>Smax)
{
Smax=P+Smin;
poz=poz1+lung1;
lung=n-lung1;
}
}
int main()
{
citire();
parc();
fout<<Smax<<" "<<poz<<" "<<lung<<"\n";
fout.close();
return 0;
}