Cod sursa(job #2888735)
| Utilizator | Data | 11 aprilie 2022 19:46:37 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.67 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
const int Nmax = 5e6 + 5;
int A[Nmax], D[Nmax];
int main()
{
int N, K;
in >> N >> K;
for(int i = 1; i <= N; ++i)
in >> A[i];
int back = 1, front = 0; // heresy but it is what it is
long long ans = 0;
for(int i = 1; i <= N; ++i)
{
while(back <= front && A[i] <= A[D[front]])
front--;
front++;
D[front] = i;
if(i >= K)
{
ans += A[D[back]];
if(D[back] == i - K + 1)
back++;
}
}
out << ans;
return 0;
}
