Cod sursa(job #59544)

Utilizator crawlerPuni Andrei Paul crawler Data 9 mai 2007 18:10:19
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>

#define Nmax 200011
#define Qmax 400012

long long s[Qmax];

int main()
 {
  int n,i,tmp;
  long long Smax = -2000000100, S, SS;
  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("%lld %d", &a,&tmp);
    if(tmp)
     s[i] = + a;
      else
     s[i] = - a;
   }

  min = 0;
  p = 0;
  S = 0;
  

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

  min = 0;
  p = 0;
  SS = 0;

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

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

  return 0;
 }