Cod sursa(job #2107558)

Utilizator MacoveiTiberiumacovei tiberiu MacoveiTiberiu Data 17 ianuarie 2018 15:25:49
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
#include<deque>
#define mp make_pair

using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
deque<pair<int, int> >dq;
long long int v, k, n, suma=0;
int main(){

	cin >> n >> k;

	for (int i = 1; i <= k; i++) {

        cin>>v;
		pair<int, int>x = mp(v, i);
		while (!dq.empty() && dq.back().first > v ){

			dq.pop_back();

		}
		dq.push_back(x);

	}
	suma+=dq.front().first;
	for (int i = k + 1; i <= n; i++){

        cin>>v;
		while (dq.front().second <= i - k){

			dq.pop_front();

		}
		pair<int, int>x = mp(v, i);
		while (!dq.empty() && dq.back().first > v){

			dq.pop_back();

		}
		dq.push_back(x);
		suma+=dq.front().first;

	}
    cout<<suma;
}