Cod sursa(job #2646378)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 31 august 2020 22:07:51
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#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", &currentno);
		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;
}