Cod sursa(job #1220608)

Utilizator ptquake10ptquake10 ptquake10 Data 17 august 2014 21:10:39
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <deque>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <fstream>
#include <map>
using namespace std;
#define MAX 1000001

int n, k;
long long sol;

struct per{
	int p, v;
	per() {
		p=0;
		v=0;
	}
	per(int p, int v) {
		this->p=p;
		this->v=v;
	}
};

deque<per> d;

void add(per a) {
	while (d.size() && d.front().p <= a.p - k) d.pop_front();
	while (d.size() && d.back().v >= a.v) d.pop_back();
	d.push_back(a);
}

int main() {
	int x;
	
	freopen("deque.in","r",stdin);	
	freopen("deque.out","w",stdout);
		
	scanf("%d %d", &n, &k);
	for (int i = 1; i < k; i++) {
		scanf("%d", &x);
		add(per(i,x));
	}
	for (int i = k; i <= n; i++) {
		scanf("%d", &x);
		add(per(i,x));
		sol += d.front().v;
	}
	
	cout << sol;
		
	return 0;
}