Cod sursa(job #1387566)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 14 martie 2015 14:28:09
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int main() {
	ifstream in("secventa.in");

	unsigned n,k;
	in >> n >> k;

	vector<int> values(n);
	for(int i = 0; i < n; ++i) {
		in >> values[i];
	}

	int max_value = -(1<<23);
	unsigned max_ind;

	deque<unsigned> dq;

	for(int i = 0; i < n; ++i) {
		while(!dq.empty() && values[dq.back()] > values[i])
			dq.pop_back();

		dq.push_back(i);

		while(!dq.empty() && dq.front() <= i-k)
			dq.pop_front();

		if(i >= k && values[dq.front()] > max_value) {
			max_value = values[dq.front()];
			max_ind = i;
		}
	}

	ofstream out("secventa.out");
	out << max_ind-k+2 << ' ' << max_ind+1 << ' ' << max_value << '\n';

	return 0;
}