Cod sursa(job #269367)

Utilizator Addy.Adrian Draghici Addy. Data 2 martie 2009 20:32:42
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
#define DIM 200001

int v[2*DIM],S[2*DIM];
long n,i,j,x,max,begin,L,beginmax,Lmax;

int main(){

  FILE *f = fopen("buline.in", "r");
  FILE *g = fopen("buline.out", "w");

  fscanf(f,"%ld",&n);

  j = n+1;

  for (i=1; i<=n; i++) {
    fscanf(f,"%d",&v[i]);
    fscanf(f,"%ld",&x);
    if (!x)
      v[i] *= -1;
    if (j<=2*n-1)
      v[j] = v[i];
    j++;
  }

  S[1] = v[1];
  max = v[1];
  L = 1;
  begin = 1;

  for (i=2; i<=2*n-1; i++) {
    if (S[i-1] + v[i] >= v[i]) {
      S[i] = S[i-1] + v[i];
      L++;
    }
    else {
      S[i] = v[i];
      L = 1;
      begin = i;
    }

    if ( (S[i] >= max) && (L <= n) ) {
      max = S[i];
      beginmax = (begin%n==0?n:begin%n);
      Lmax = L;
    }
  }

  fprintf(g,"%ld %ld %ld",max,beginmax,Lmax);

  fclose(f);
  fclose(g);

  return 0;
}