Cod sursa(job #1109633)

Utilizator TeOOOVoina Teodora TeOOO Data 17 februarie 2014 14:00:05
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
//Include
#include <stdio.h>
#include <deque>
#include <utility>
using namespace std;

FILE *in, *out;

//Definitii
#define pere pair<int, int>
#define mp make_pair
#define pb push_back
#define popb pop_back
#define popf pop_front

//Variabile
int num, dif;
int val;
int sum;

deque <pere> fructe;

//Main
int main()
{
	in = fopen("deque.in", "rt");
	out = fopen("deque.out", "wt");
    fscanf(in,"%d%d", &num, &dif);

    for(int i=1; i<dif; ++i)
    {
        fscanf(in,"%d", &val);
        while(!fructe.empty() && val < fructe.back().first)
            fructe.popb();
        fructe.pb(mp(val, i));
    }

    for(int i=dif; i<=num; ++i)
    {
        if(i - fructe.front().second == dif)
            fructe.popf();

        fscanf(in,"%d", &val);
        while(!fructe.empty() && val < fructe.back().first)
            fructe.popb();
        fructe.pb(mp(val, i));

        sum += fructe.front().first;
    }

    fprintf(out,"%d\n", sum);

	fclose(in);
	fclose(out);
	return 0;
}