Cod sursa(job #2831206)
Utilizator | Data | 10 ianuarie 2022 22:25:09 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <fstream>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
long long s;
int n, k, i, u, p, v[5000005], d[5000005];
int main(){
fin >> n >> k;
for (i = 1; i <= n; i++)
fin >> v[i];
d[1] = 1;
p = 1;
u = 1;
for (i = 2; i <= n; i++){
while (p <= u && v[i] <= v[ d[u] ])
u--;
u++;
d[u] = i;
if (i-d[p] == k)
p++;
if (i>=k)
s += v[ d[p] ];
}
fout << s;
return 0;
}