Cod sursa(job #2877435)

Utilizator mihai_sabouSabou Mihai mihai_sabou Data 24 martie 2022 18:56:33
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

long long v[5000001], s = 0;
deque <pair<int, int>> d;

int main() {
	int n, subsir;
	in >> n >> subsir;

	for (int i = 1; i <= n; ++i) {
		in >> v[i];
	}

	for (int i = 1; i <= n; ++i) {
		if (!d.empty() && (i - d.front().second) >= subsir)
			d.pop_front();
		if (!d.empty()) {
			if (v[i] <= d.back().first) {
				while (!d.empty() && v[i] <= d.back().first)
					d.pop_back();
			}

			d.push_back(make_pair(v[i], i));
		}
		else
			d.push_back(make_pair(v[i], i));

		if (i >= subsir && !d.empty())
			s += d.front().first;
	}

	out << s;
}