Cod sursa(job #68332)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 27 iunie 2007 16:32:21
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
#include<limits.h>

long n, v[200002], max=INT_MIN, min=INT_MAX, sum, pix, pin, pi, pfx, pfn, pf;

void citire()
{
  freopen("buline.in","r",stdin);
  freopen("buline.out","w",stdout);
  scanf("%ld", &n);

  long i, j, s;

  for (i=1; i<=n; i++)
    {
      scanf ("%ld %ld",&v[i],&s);
      if (s==0) v[i]*=(-1);
      sum+=v[i];
    }

}

void suma()
{
  long sc, i, pi, pf;
  sc=v[1];
  pi=pf=1;
  max=sc;
  for (i=2; i<=n; i++)
    {
      if (sc<=0) { pf=i-1; pi=i; sc=v[i];}
	else sc+=v[i];
      if (sc>max) { max=sc; pix=pi; pfx=i;}
    }
}

void smin()
{
  long sc, i, pi, pf;
  sc=v[1];
  pi=pf=1;
  min=sc;
  for (i=2; i<=n; i++)
     {
       if (sc>=0) { pf=-1; pi=i; sc=v[i];}
	 else sc+=v[i];
       if (sc<min) { min=sc; pin=pi; pfn=i;}
     }
}

int main()
{
  citire();
  suma();
  smin();
  long maxim;
  if (max>sum)
    if (max>sum-min) { maxim=max; pi=pix; pf=pfx;}
      else { maxim=sum-min;  pi=pfn+1; pf=pin-1;}
   else if (sum>sum-min) { maxim=sum;pi=1; pf=n;}
	  else { maxim=sum-min;  pi=pfn+1; pf=pin-1;}
  long lung;
  if (pi<pf) lung=pf-pi+1;
    else lung=pf+(n-pi+1);
  printf("%ld %ld %ld",maxim, pi, lung);
  return 0;
}