Cod sursa(job #1311609)

Utilizator Vele_GeorgeVele George Vele_George Data 8 ianuarie 2015 13:54:39
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <deque>
#include <fstream>

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

struct nr
{
    int val,i;
}aux,x;

deque<nr> DQ;

void add(nr x)
{
    while(!DQ.empty() && x.val<DQ.back().val)
    {
        DQ.pop_back();
    }
    DQ.push_back(x);
}
int n,k;
long long sum;
int main()
{
    f>>n>>k;
    for(int i=1; i<=k; i++)
    {
        f>>x.val;
        x.i=i;
        add(x);
    }
    cerr << DQ.front().val << " ";
    sum+=DQ.front().val;
    for(int i=k+1; i<=n; i++)
    {
        f>>x.val;
        x.i=i;
        if (DQ.front().i<=i-k)
        {
            DQ.pop_front();
        }

        add(x);
        sum+=DQ.front().val;
        cerr << DQ.front().val << " ";
    }
    g<<sum;
    return 0;
}