Cod sursa(job #1884979)

Utilizator FrequeAlex Iordachescu Freque Data 19 februarie 2017 15:31:25
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream fin("maxp.in");
ofstream fout("maxp.out");

const int NMAX = 200000 + 5;

deque <int> dq;

int n, k;
long long int sum;
int v[NMAX], grup_st[NMAX], grup_dr[NMAX];
long long int ans = 0, ans_cnt = 1;

void read()
{
    fin >> n >> k;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
}

int main()
{
    read();

    for (int i = 1; i <= n; ++i)
    {
        //scoti de la inceput cat e nevoie
        //scoti de la sfarsit a.i sa fie cresc
        //add
        //verif daca i >= k
        while (dq.front() < i - k + 1)
            dq.pop_front();

        while (v[dq.back()] > v[i])
            dq.pop_back();

        dq.push_back(i);

        if (i >= k)
            sum += v[dq.front()];
    }
    fout << sum;
    return 0;
}