Cod sursa(job #218949)

Utilizator log2cont de teste log2 Data 4 noiembrie 2008 12:03:22
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#define DIM 50002

long long A[DIM],K[DIM],V[DIM],L[DIM];
long long n,k,i,max,s,pMax;


int main(){
  FILE *f = fopen("secv2.in","r");
  fscanf(f,"%lld %lld",&n,&k);
  for (i=1;i<=n;i++) {
    fscanf(f,"%lld",&V[i]);
    if (i<=k)
      s+=V[i];
    if (i==k){
      A[i] = s;
      K[i] = s;
    }
    if (i>k) {
      K[i] = K[i-1]+V[i]-V[i-k];
      if ((A[i-1]+V[i]>=K[i]) && (A[i-1]+V[i]>=A[i-1]+V[i]-V[i-1-L[i-1]+1])){
	A[i] = A[i-1]+V[i];
	L[i] = L[i-1]+1;
      } else if ((K[i]>=A[i-1]+V[i]) && (K[i]>=A[i-1]+V[i]-V[i-1-L[i-1]+1])){
	A[i] = K[i];
	L[i] = k;
      } else if ((A[i-1]+V[i]-V[i-1-L[i-1]+1]>=A[i-1]+V[i]) && (A[i-1]+V[i]-V[i-1-L[i-1]+1]>A[i-1]+V[i])){
	A[i] = A[i-1]+V[i]-V[i-1-L[i-1]+1];
	L[i] = L[i-1];
      }
    }
  }
  fclose(f);
  max = A[k];
  pMax = k;
  for (i=k+1;i<=n;i++)
    if (A[i]>max){
      max = A[i];
      pMax = i;
    }
  FILE *g = fopen("secv2.out","w");
  fprintf(g,"%lld %lld %lld",pMax-L[pMax]+1,pMax,max);
  fclose(g);
  return 0;
}