Pagini recente » Cod sursa (job #1463621) | Cod sursa (job #181989) | Cod sursa (job #353473) | Cod sursa (job #2262202) | Cod sursa (job #1220608)
#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;
}