Cod sursa(job #541209)

Utilizator ingridutz95Botescu Ingrid ingridutz95 Data 24 februarie 2011 21:39:38
Problema Deque Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream>
#define maxn 5000010
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k,a[maxn],deque[maxn];
int front=1,back,i;//initializare back<=front din care rezulta ca deque-ul nu are niciun element (este vid)
long long S;
int main(){
	f>>n>>k;  
	for(i=1;i<n;i++) f>>a[i];//citeste sirul dat
	for(i=1;i<=n;i++) {
		while(front<=back && a[i]<=a[deque[back]]) back--; //cat timp elementul curent este mai mic decat ultimul element din deque, eliminam pozitia ultimului element din deque
			deque[++back]=i; //adaugam pozitia elementului curent in deque
		if(deque[front]==i-k) front++; //daca elementul minim coincide cu cel de pe pozitia i-k, ii eliminam pozitia din deque, deoarece acesta nu mai conteaza pentru pasii >=i
		if(i>=k) S+=a[deque[front]];
	}
	g<<S;
	g.close();
	return 0;
}