Cod sursa(job #404888)

Utilizator toniobFMI - Barbalau Antonio toniob Data 26 februarie 2010 20:57:50
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <deque>

using namespace std;
int N,K;
deque <pair<int,int> > D;

int main(){
	ifstream in("secventa.in");
	ofstream out("secventa.out");
	in>>N>>K;
	int Max=-40000,i,de_citit;
	for(i=0;i<K;++i){
		in>>de_citit;
		for(;!D.empty()&&D.back().first>de_citit;D.pop_back()){}
		D.push_back(make_pair(de_citit,i));
	}
	int inceput=1,sfarsit=K;
	for(i=K;i<N;++i){
		if(D.front().first>Max){
			Max=D.front().first;
			inceput=i-K+1;
			sfarsit=i;
		}
		if(D.front().second<=i-K){
			D.pop_front();
		}
		in>>de_citit;
		for(;!D.empty()&&D.back().first>de_citit;D.pop_back()){}
		D.push_back(make_pair(de_citit,i));
	}
	if(D.front().first>Max){
		Max=D.front().first;
		inceput=i-K+1;
		sfarsit=i;
	}
	out<<inceput<<" "<<sfarsit<<" "<<Max;
	return 0;
}