Cod sursa(job #1465220)

Utilizator L.DanielLungu Daniel L.Daniel Data 26 iulie 2015 19:33:23
Problema Deque Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <deque>
using namespace std;

const int MAX = 5000010;
const int MAXC = 100010;
long long N, K;
long long S;
char c[MAXC];
long long p = MAXC - 1;
long long x;
deque< pair<int, long long> > Q;

void Read();
void Get(long long& x);
void Next();

int main()
{
	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);

	int i, j;

	Read();
	for (i = 1; i <= K - 1; i++)
	{
		Get(x);
		while (!Q.empty() && x < Q.back().second)
			Q.pop_back();
		Q.push_back(make_pair(i, x));
	}

	for (i = K; i <= N; i++)
	{
		Get(x);
		while (!Q.empty() && Q.front().first <= i - K)
			Q.pop_front();

		while (!Q.empty() && x < Q.back().second)
			Q.pop_back();
		Q.push_back(make_pair(i, x));

		S += Q.front().second;
	}

	printf("%lld\n", S);

	fclose(stdin);
	fclose(stdout);
	return 0;
}

void Read()
{
	int i;
	Get(N);
	Get(K);
}

void Get(long long& x)
{
	bool sgn = 0;
	for (; c[p] < '0' || c[p] > '9'; Next())
		if (c[p] == '-')
			sgn = 1;
	for (x = 0; c[p] >= '0' && c[p] <= '9'; Next())
		x = x * 10 + (c[p] - '0');
	if (sgn)
		x = -x;
}

void Next()
{
	if (++p == MAXC)
	{
		std::fread(c, 1, MAXC, stdin);
		p = 0;
	}
}