Cod sursa(job #130983)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 2 februarie 2008 19:30:26
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#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;
}