Cod sursa(job #17622)

Utilizator alex_damianDamian Alexandru alex_damian Data 16 februarie 2007 14:35:27
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>

#define FIN "secv2.in"
#define FOUT "secv2.out"
#define MAXN 50001

long long s[MAXN], min[MAXN], val;
long n, k, i, j, x, poz[MAXN], pi, pf;


int main () {
	freopen(FIN, "r", stdin);
  freopen(FOUT, "w", stdout);
  scanf("%ld %ld", &n, &k);
  for (i=1; i<=n; i++) {
     scanf("%ld", &x);
     s[i] = s[i-1] + x;
     if (min[i-1] > s[i]) {
       min[i] = s[i];
       poz[i] = i;
     } else {
       min[i] = min[i-1];
       poz[i] = poz[i-1];
     }
  }
  pf = k;
  pi = 1;
  val = s[k];
	for (i=k+1; i<=n; i++) {
     if (val < s[i] - min[i-k]) {
       pf = i;
       pi = poz[i-k];
       val = s[i] - min[i-k];
     }
  }
	printf("%ld %ld %lld\n", pi+1, pf, val);
  return 0;
}