Cod sursa(job #3171275)
Utilizator | Craciun Mihai Arklahhis | Data | 18 noiembrie 2023 17:20:30 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
#define NMAX 5000000
#define VALMAX 10000000
int n,x[NMAX+1],dq[NMAX+1],k,f,b;
long long s;
int main()
{
fin >> n >> k;
for (int i=1; i<=n; i++)
fin >> x[i];
f=1;
b=0;
for (int i=1; i<=n; i++)
{
while (f<=b && x[i]<=x[dq[b]])
b--;
b++;
dq[b]=i;
if (dq[f]==i-k)
f++;
if (i>=k)
s+=x[dq[f]];
}
fout << s;
return 0;
}