Cod sursa(job #474788)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 5 august 2010 00:36:02
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<fstream>
#include<deque>
#include<iostream>

using namespace std;
int N,K;
long long S;

deque<pair<int,int> > Q;


void citire()
{
	ifstream fin("deque.in");
	ofstream fout("deque.out");
	fin>>N>>K;
	int x;
	
	for(int i=1;i<=N;i++)
	{
		fin>>x;
		if(!Q.empty())
			while(Q.back().first > x )
				Q.pop_back();

				
		Q.push_back(make_pair(x,i));
		
			
		if(i - Q.front().second >= K)
		{
			Q.pop_front();
		}
	
		if(i>=K) S+=Q.front().first;
	}
	
	fout<<S<<"\n";
	fin.close();
	fout.close();
	
}

int main(int argc, char *argv[])
{
	citire();

}