Cod sursa(job #3137130)
Utilizator | Alexandru Rotariu Polsca | Data | 11 iunie 2023 13:38:50 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int v[5000001], dq[5000001];
int main() {
int n, k, st=0, dr=0;
long long s = 0;
fin >> n >> k;
for (int i = 1; i <= n; i++)
fin >> v[i];
for (int i = 1; i <= n; i++) {
while (st <= dr && v[i] <= v[dq[dr]] )dr--;
dr++;
dq[dr] = i;
if (k - i < 1 - dq[st])st++;
if (i >= k)s += v[dq[st]];
}
fout << s;
return 0;
}