Cod sursa(job #662111)

Utilizator informatician28Andrei Dinu informatician28 Data 15 ianuarie 2012 20:54:30
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<fstream> 
#include<deque> 
#define NMAX 500005
using namespace std; 

ifstream in("secventa.in"); 
ofstream out("secventa.out"); 

int N, K, A[NMAX]; 
deque< int > D;
int main()
{
	int i, baza, S = -100000, Si;
	in >> N >> K; 
	for(i = 1; i <= N; i++) 
		in >> A[i]; 
	
	for(i = 1; i <= N; i++) 
	{
		while(!D.empty() and A[i] <= A[ D.back() ]) 
			{
				D.pop_back();
		}
		
		D.push_back(i); 
		
		if(D.front() == i-K) D.pop_front(); 
		
		if(i >= K) 
		{
			baza = A[ D.front() ]; 
			if( baza > S) 
			{
			S = baza; 
			Si = i; 
			}
		}
	}
	
	out << Si-K+1 << " " << Si << " " << S; 
}