Cod sursa(job #2714439)
Utilizator | Data | 1 martie 2021 20:03:10 | |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int dq[5000002];
long long v[5000002];
int main()
{
long long suma;
int n, k;
int st, dr = -1;
in>>n>>k;
for (int i = 1; i <= n; i++){
in >> v[i];
if (st <= dr && dq[st] == i - k)
st++;
while (st <= dr && v[i] <= v[dq[dr]])
dr--;
dq[++dr] = i;
if (st <= dr && i >= k)
suma += v[dq[st]];
}
out<<suma;
return 0;
}