Cod sursa(job #183241)

Utilizator alecmanAchim Ioan Alexandru alecman Data 21 aprilie 2008 20:58:39
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<cstdio>
#include<deque>

using namespace std;

#define INPUT "secventa.in"
#define OUTPUT "secventa.out"
#define INFI -32000

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

typedef struct secv
{
  int sec;
  long poz;
};

long N, K;
deque<secv> DQE;

void readValues()
{
  fscanf(fin, "%ld %ld", &N, &K);
}

void solveFunction()
{
  long Max = INFI, Pinit = -1;
  secv Y;
  int X;

  for(long i = 1; i <= N; ++i)
  {
    fscanf(fin, "%d", &X);

    while(!DQE.empty() && DQE.back().sec > X)
      DQE.pop_back();

    Y.sec = X;
    Y.poz = i;

    DQE.push_back(Y);

    while(!DQE.empty() && DQE.front().poz <= i - K)
      DQE.pop_front();

    if( i >= K)
    {
      if(Max < DQE.front().sec)
      {
        Max = DQE.front().sec;
	Pinit = i;
      }
    }
  }

  fprintf(fout, "%ld %ld %ld\n", Pinit - K + 1, Pinit, Max);
}

int main()
{
  readValues();

  solveFunction();

  fclose(fin);
  fclose(fout);

  return 0;
}