Cod sursa(job #2191353)

Utilizator ibogdan25Ilie Ionut ibogdan25 Data 2 aprilie 2018 17:31:39
Problema Deque Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
// SortChar.cpp : Defines the entry point for the console application.
//

#include <queue>
#include <iostream>
#include <string>
#include <fstream>

using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int maxSlidingWindow(vector<int>& nums, int k) {
	deque<int> Qi_min;
	int difference_max = -1;
	for (int i = 0; i < k; i++) {
		while (!Qi_min.empty() && nums[i] <= nums[Qi_min.back()]) {
			Qi_min.pop_back();
		}
		Qi_min.push_back(i);
	}
	vector<int> solution(nums.size());
	int sum = 0;
	for (int i = k; i <= nums.size(); i++) {
		sum += nums[Qi_min.front()];
		if (i == nums.size()) break;
		while (!Qi_min.empty() && Qi_min.front() < i - k) {
			Qi_min.pop_front();
		}
		while (!Qi_min.empty() && nums[i] <= nums[Qi_min.back()]) {
			Qi_min.pop_back();
		}

		Qi_min.push_back(i);
	}
	return sum;
}
int main()
{
	//5, 9, 4, 7, 4, 1
	int n = 0, k = 0;
	vector<int> V;
	f >> n >> k;
	for (int i = 0, x = 0; i < n; i++) {
		f >> x;
		V.push_back(x);
	}
	g << maxSlidingWindow(V, k);

    return 0;
}