Cod sursa(job #1495569)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 3 octombrie 2015 11:27:45
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <fstream>
using namespace std;

struct a{
    int v, poz;
} v[5000000];

int n, k, q, st = -1, dr = 0;
long long r = 0;

int main(){
    ifstream in("deque.in");
    ofstream out("deque.out");
    in >> n >> k >> v[0].v;
    v[0].poz = 0;
    for (int i = 1; i < n; i++){
        in >> q;
        while(st != dr && q <= v[dr].v)
            dr--;
        v[++dr].v = q;
        v[dr].poz = i;
        if (v[dr].poz - v[st + 1].poz >= k)
            st++;
        if(i + 1 >= k)
            r += v[st + 1].v;
    }
    out << r;


    return 0;
}