Cod sursa(job #355752)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 12 octombrie 2009 01:34:06
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>

#define FISIN     "secventa2.in"
#define FISOUT    "secventa2.out"
FILE *fin, *fout;

#define MAXN 50000

int n, k;
int a[MAXN], p[MAXN], max[MAXN];

int main() {
  fin = fopen(FISIN, "rt");
  fout = fopen(FISOUT, "wt");

  fscanf(fin, "%d %d", &n, &k);
  for (int i = 0; i < n; ++i)
    fscanf(fin, "%d", a + i);

  p[0] = a[0]; for (int i = 1; i < n; ++i) p[i] = p[i - 1] + a[i];

  max[n - 1] = n - 1;
  for (int i = n - 2; i >= 0; --i)
    if (p[max[i + 1]] > p[i])
      max[i] = max[i + 1];
    else
      max[i] = i;

  int best_score = p[max[k - 1]], best_start = 0, best_end = max[k - 1];

  for (int i = 0; i <= n - k; ++i) {
    int end = max[i + k - 1];
    int score = p[end] - p[i];
    if (score > best_score) {
      best_score = score;
      best_start = i + 1;
      best_end = end;
    }
  }

  fprintf(fout, "%d %d %d\n", best_start + 1, best_end + 1, best_score);

  fclose(fout);
  fclose(fin);
  return 0;
}