Cod sursa(job #2257797)

Utilizator DRLDRLRaul Ronald Galea DRLDRL Data 10 octombrie 2018 15:23:50
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#pragma once

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<deque>

using namespace std;

ifstream fin("deque.in");
ofstream fout("deque.out");

deque<int> secventa;
vector<int> elems;

int sum = 0;

void a(int n, int k) {
	secventa.push_back(0);
	for (int i = 1; i < n; i++) {

		while (elems[i] <= elems[secventa.back()]) {
			secventa.pop_back();
			if (secventa.empty())
				break;
		}

		secventa.push_back(i);

		if (i + 1 >= k) {
			sum += elems[secventa.front()];
		}

		if (secventa.front() == i - k + 1) {
			secventa.pop_front();
		}
	}
}

int main() {
	int n, k;
	fin >> n >> k;
	elems.resize(n);
	for (int i = 0; i < n; i++)
		fin >> elems[i];
	a(n, k);
	fout << sum;
	return 0;
}