Cod sursa(job #267851)

Utilizator Addy.Adrian Draghici Addy. Data 28 februarie 2009 11:53:22
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#define DIM 50002
#define INF 1250000002

int v[DIM],S[DIM],MIN[DIM],P[DIM];
long n,k,i,begin,end,ibegin,iend;
long long max;

//S[i] = vectorul de sume partiale
//MIN[i] = cel mai mic S de la 1 la i
//P[i] = pozitia pe care e MIN[i]

int main(){

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

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

  for (i=1; i<=n; i++)
    fscanf(f,"%d",&v[i]);

  S[1] = v[1];
  MIN[1] = S[1];
  P[1] = 1;
  max = -INF;

  for (i=2; i<=n; i++) {

    S[i] = S[i-1] + v[i];
    if (S[i] < MIN[i-1]) {
      MIN[i] = S[i];
      P[i] = i;
    }
    else {
      MIN[i] = MIN[i-1];
      P[i] = P[i-1];
    }

    if (i >= k) {
      if (S[i]-MIN[i-k] > max) {
	max = S[i]-MIN[i-k];
	begin = P[i-k]+1;
	end = i;
      }
      if (S[i] > max) {
	max = S[i];
	begin = 1;
	end = i;
      }
    }
  }

  fprintf(g,"%ld %ld %lld\n",begin,end,max);

  fclose(f);
  fclose(g);

  return 0;
}