Cod sursa(job #632805)

Utilizator johnny2008Diaconu Ion johnny2008 Data 12 noiembrie 2011 12:59:33
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<fstream>
#include<iostream>
using namespace std;

#define maxn 5000001
int n,k,sum=0;
int deque[maxn];
int timp[maxn];
int cat;
int main(){
	ifstream f("deque.in");
	ofstream g("deque.out");
	f>>n>>k;
	int j,t;
	f>>j;
	short ok=0;
	deque[1]=j;
	timp[1] = 1;
	int ct=1;
	int first = 1;
	for(int i=2;i<=n;i++){
		f>>j;
		while(j<deque[ct] && ct>=first)
			ct--;
		deque[++ct]=j;
		timp[ct] = i;
		
		if( i - timp[ first ] >= k )
			first++;
		
		if(i>=k){
			//cout<<deque[first]<<"\n";
			sum=sum+deque[first];
		}
	}
	g<<sum<<'\n';
	return 0;
}