Cod sursa(job #276363)

Utilizator n3msizN3msiz n3msiz Data 11 martie 2009 09:16:46
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
#define DIM 200001

long int v[DIM];
long int x[DIM];

long int n,i,iMin,iMax,iMin1,iMax1,max,s,sum1,sum2,sTot,iMin2,iMax2;
int t;

int main(){
  FILE *f = fopen("buline.in","r");
  fscanf(f,"%ld",&n);
  for (i=1;i<=n;i++) {
    fscanf(f,"%ld %d",&v[i],&t);
    if (t==0) {
      v[i]=-v[i];
    }
  }
  fclose(f);

//secventa de suma maxima
  x[1]=v[1];
  for (i=2;i<=n;i++)
    if (x[i-1]+v[i]>v[i])
      x[i]=x[i-1]+v[i];
    else
      x[i]=v[i];

  iMax = 1;
  max = x[1];
  for (i=2;i<=n;i++)
    if (x[i]>max) {
      max = x[i];
      iMax = i;
    }
  s=0;
  for (iMin=iMax;iMin>=1;iMin--) {
    s+=v[iMin];
    if (s==max)
      break;
  }

  sum1=s;
  iMin1 = iMin;
  iMax1 = iMax;



//secventa de suma minima
  x[1]=1;
  for (i=2;i<=n;i++)
    if (x[i-1]+v[i]<v[i])
      x[i]=x[i-1]+v[i];
    else
      x[i]=v[i];

  iMax = 1;
  max = x[1];
  for (i=2;i<=n;i++)
    if (x[i]<max) {
      max = x[i];
      iMax = i;
    }
  s=0;
  for (iMin=iMax;iMin>=1;iMin--) {
    s+=v[iMin];
    if (s==max)
      break;
  }
  iMin2 = iMin;
  iMax2 = iMax;
  sum2=s;

  sTot = 0;
  for (i=1;i<=n;i++)
    sTot+=v[i];


  FILE *g = fopen("buline.out","w");
  if (sum1>sTot-sum2) {
    fprintf(g,"%ld %ld %ld",sum1,iMin1,iMax1-iMin1+1);
  } else {
    fprintf(g,"%ld %ld %ld",sTot-sum2,iMax2+1,n-(iMax2-iMin2+1));
  }

  fclose(g);

  return 0;
}