Pagini recente » Cod sursa (job #2804399) | Cod sursa (job #1142299) | Cod sursa (job #2870787) | Cod sursa (job #148704) | Cod sursa (job #2646378)
#include <cstdio>
using namespace std;
int main() {
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int n, k, currentback = 0, currentfront = 0, currentno;
long long totalmin = 0;
scanf("%d%d", &n, &k);
int numbers[k+1], numberindexes[k+1];
for(int i=0; i<=k; ++i)
numbers[i] = numberindexes[i] = 0;
scanf("%d", &numbers[0]);
numberindexes[0] = 1;
for(int i=2; i<=n; ++i) {
scanf("%d", ¤tno);
while(currentback != currentfront && currentno <= numbers[currentback])
{
--currentback;
if (currentback < 0)
currentback = k;
}
if (currentback == currentfront && numbers[currentback] >= currentno)
--currentback;
++currentback;
currentback %= (k+1);
numbers[currentback] = currentno;
numberindexes[currentback] = i;
if (numberindexes[currentfront] <= i-k) {
++currentfront;
currentfront %= (k+1);
}
if (i>=k) {
totalmin += numbers[currentfront];
}
}
printf("%lld\n", totalmin);
return 0;
}