Cod sursa(job #716195)

Utilizator RobertBBadea Corneliu Robert RobertB Data 18 martie 2012 14:03:47
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

ifstream f("deque.in");
ofstream g("deque.out");

int sir[5000000], suma;
deque <int> coada;
int N,K;

int main()
{
	int i;
	f>>N>>K;
	for(i = 0; i < K; i++) {
		f>>sir[i];
		while (!coada.empty() && sir[coada.front()] > sir[i]){
		   coada.pop_front();
		}
		if (!coada.empty() && coada.back() + K <= i){
			coada.pop_back();
		}
		coada.push_front(i);
	}
	suma += sir[coada.back()];
    for (i = K; i < N; i++){
        f>>sir[i];
        while (!coada.empty() && sir[coada.front()] > sir[i]){
		   coada.pop_front();
		}
		if (!coada.empty() && coada.back() + K <= i){
			coada.pop_back();
		}
		coada.push_front(i);
        suma += sir[coada.back()];
    }
	g<<suma;
	
}