Cod sursa(job #53087)

Utilizator crawlerPuni Andrei Paul crawler Data 20 aprilie 2007 21:33:56
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>

#define Nmax 200001
#define Qmax 400002

int s[Qmax];

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

  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("%d %d %d", Smax,Pmax,L);

  return 0;
 }