Cod sursa(job #486688)

Utilizator dcm9000Dinu Cristian Mircea - UPB dcm9000 Data 22 septembrie 2010 14:37:01
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <string>
#include <deque>

using namespace std;

#define FILE_IN "secventa.in"
#define FILE_OUT "secventa.out"

int N,K;
int V[500000];

int main()
{
	FILE* fisIn = fopen(FILE_IN, "r");
	ofstream fisOut(FILE_OUT);

	fscanf(fisIn, "%d %d", &N, &K);
	for (int i=0; i<N; i++) fscanf(fisIn, "%d", V+i);

	int best = V[0];
	int start = 0;

	deque<int> deq;
	for (int i=0; i<N; i++)
	{
		while (!deq.empty() && (deq.front() <= i-K)) deq.pop_front();
		int elem = V[i];
		while (!deq.empty() && (V[deq.back()] >= elem)) deq.pop_back();
		deq.push_back(i);

		if ((i>=K) && (V[deq.front()] > best))
		{
			best = V[deq.front()];
			start = i-K+1;
		}
	}

	fisOut << (start+1) << " " << (start+K) << " " << best;
}