Cod sursa(job #355046)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 10 octombrie 2009 07:45:35
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>

#define MAXN      500000

#define FISIN     "secventa.in"
#define FISOUT    "secventa.out"

FILE *fin, *fout;

int key[MAXN];
short value[MAXN];
int start, stop;

void add(int k, short v) {
  while (stop > start && v < value[stop - 1]) --stop;
    value[stop] = v; key[stop] = k; ++stop;
}
void del(int k) {
    if (key[start] == k) ++start;
}
int min() { return value[start]; }

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

  int m, n, k, a, start; fscanf(fin, "%d %d", &n, &k);
  for (int i = 0; i < k; ++i)  {
    fscanf(fin, "%d", &a);
    add(i, a);
  }
  int best_start = 0; int best_base = min();
  
  for (int i = k; i < n; ++i) {
    fscanf(fin, "%d", &a);
    start = i - k;
    del(start);
    add(i, a);
    m = min(); 
    if (m > best_base) {
      best_base = m;
      best_start = start + 1;
    }
  }

  best_start++;
  fprintf(fout, "%d %d %d\n", best_start, best_start + k - 1, best_base);

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