Cod sursa(job #2176284)
Utilizator | Data | 16 martie 2018 22:11:45 | |
---|---|---|---|
Problema | Deque | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
#include <cstdio>
#define NMAX 500002
using namespace std;
int n, k, V[NMAX], Deque[NMAX];
int Front, Back;
long long Sum;
int main()
{
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
scanf("%d%d", &n, &k);
for(int i=1; i<=n; i++)
scanf("%d", &V[i]);
Front=1;Back=0;
for(int i=1; i<=n; i++)
{
while(Front<=Back&&V[i]<=V[Deque[Back]]) Back--;
Deque[++Back]=i;
if(Deque[Front]==i-k) Front++;
if(i>=k)
Sum=Sum+V[Deque[Front]];
}
printf("%lld\n", Sum);
return 0;
}