Cod sursa(job #3001491)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 13 martie 2023 18:32:41
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
//Ilie Dumitru
#include<cstdio>
#include<deque>
const int NMAX=5000005;

int N, K, v[NMAX];
std::deque<int> dq;

inline void process(int i)
{
	if(dq.front()==i-K)
		dq.pop_front();
	while(!dq.empty() && v[dq.back()]>=v[i])
		dq.pop_back();
	dq.push_back(i);
}

int main()
{
	FILE *f=fopen("deque.in", "r"), *g=fopen("deque.out", "w");
	int i;
	long long int ans=0;

	fscanf(f, "%d%d", &N, &K);
	for(i=0;i<N;++i)
		fscanf(f, "%d", v+i);

	for(i=0;i<K;++i)
		process(i);
	ans=v[dq.front()];

	for(;i<N;++i)
	{
		process(i);
		ans+=v[dq.front()];
	}

	fprintf(g, "%lld", ans);

	fclose(f);
	fclose(g);
	return 0;
}