Cod sursa(job #59540)

Utilizator crawlerPuni Andrei Paul crawler Data 9 mai 2007 18:02:49
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>

#define Nmax 200011
#define Qmax 400012

long long s[Qmax];

int main()
 {
  int n,i;
  long long tmp,Smax = -2000000100;
  long long min ,a ; int p, Pmax, L;

  freopen("buline.in","r",stdin);
  freopen("buline.out","w",stdout);

  scanf("%d", &n);


  for(i=1;i<=n;++i)
   {
    scanf("%d %d", &a,&tmp);
    if(tmp)
     s[i] = s[i-1] + a;
      else
     s[i] = s[i-1] - a;
   }

  min = 0;
  p = 0;
  

  for(i=1;i<=n;++i)
   {
    if(s[i] - min > Smax)
     {
      Smax = s[i] - min;
      Pmax = p;
      L = i-p;
     }
    if(s[i] < s[min])
     {
      min = s[i];
      p = i;
     }
   }

  min = 0;
  p = 0;

  for(i=1;i<=n;++i)
   {
    if(min + s[n] - s[i-1] >= Smax)
     {
      Smax = min + s[n] - s[i-1];
      Pmax = i;
      L = n-i+1+p;
     }
    if(s[i] > min)
     {
      min = s[i];
      p = i;
     }
   }

  printf("%lld %d %d", Smax,Pmax,L);

  return 0;
 }