Cod sursa(job #935070)

Utilizator whoasdas dasdas who Data 1 aprilie 2013 14:42:30
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <deque>

using namespace std;

class Magic {
    int k;
    struct my_min
    {
        int val;
        int age;
        my_min(int v) {
            val = v;
            age = 0;
        }
    };
    deque<my_min> mins;

    public:
    Magic(int k) {
        this->k = k;
    }
    void insert(int x) {
        while (!mins.empty() && mins.back().val >= x)
            mins.pop_back();
        for (int i = 0; i < mins.size(); i++)
            mins[i].age++;
        mins.push_back(my_min(x));
        if (mins.front().age == k)
            mins.pop_front();
    }
    int get_min() {
        return mins.front().val;
    }
};

void insert(int x) {

}
int main()
{
    ifstream in("deque.in");
    ofstream out("deque.out");
    int n, k, sum = 0, x;
    in>>n>>k;

    Magic magic(k);

    for (int i = 0; i < n; i++) {
        in>>x;
        magic.insert(x);
        if (i >= k-1)
            sum += magic.get_min();
    }
    out<<sum<<endl;
    return 0;
}