Cod sursa(job #1074746)

Utilizator dan.ghitaDan Ghita dan.ghita Data 7 ianuarie 2014 22:06:16
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int v[5000002], n, k;
long long s;

struct comp
{
    bool operator() (const int &x, const int &y)
    {
        return (v[x] > v[y]);
    }
};
priority_queue<int, vector<int>,comp> h;

int main()
{
    f>>n>>k;
    for(int i=0; i<n; ++i)
        f>>v[i];
    for(int i=0; i<n; ++i)
    {
        h.push(i);
        if(i<k-1) continue;
        while(h.top()<=i-k) h.pop();
        s+=v[h.top()];
    }
    g<<s;
    return 0;
}