Cod sursa(job #2657212)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 10 octombrie 2020 09:20:37
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>

using namespace std;

typedef long long lint;

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

struct jotaro{
	int p, v;
};

int n, k;
deque<jotaro> de;

lint sum = 0;

int main(){
	// ios_base::sync_with_stdio(false);
	fin >> n >> k;
	for(int i = 0; i < n; ++i){
		jotaro a;fin >> a.v;
		a.p = i;
		while(!de.empty() && a.v < de.back().v)de.pop_back();
		if(!de.empty() && i-de.front().p >= k)de.pop_front();
		de.push_back(a);
		if(i >= k-1)sum += de.front().v;
	}
	fout << sum;
	return 0;
}