Cod sursa(job #249390)
| Utilizator | Data | 28 ianuarie 2009 12:35:23 | |
|---|---|---|---|
| Problema | Deque | Scor | 60 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.58 kb |
#include <cstdio>
#define ll long long
int N, K;
int Dq[500005], V[500005];
ll ans;
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);
for (int st = 1, dr = 0, i = 1; i <= N; ++ i) {
while (st <= dr && V[Dq[dr]] >= V[i]) -- dr;
Dq[++dr] = i;
while (st <= dr && i - Dq[st] >= K) ++ st;
if (i >= K) ans += (ll)V[Dq[st]];
}
printf ("%lld\n", ans);
return 0;
}
