Cod sursa(job #2126988)

Utilizator MaligMamaliga cu smantana Malig Data 10 februarie 2018 11:08:01
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

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

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
const int NMax = 5e6 + 5;
const int inf = 1e9 + 5;
const int mod = 9973;
using zint = int;

int N,K;
int v[NMax];

int main() {
    in>>N>>K;

    deque<int> deq;
    ll ans = 0;
    for (int i = 1;i <= N;++i) {
        in>>v[i];

        while (deq.size() && v[deq.back()] >= v[i]) {
            deq.pop_back();
        }

        deq.push_back(i);

        if (i - deq.front() + 1 > K) {
            deq.pop_front();
        }

        if (i >= K) {
            ans += v[deq.front()];
        }
    }

    out<<ans<<'\n';

    in.close();out.close();
    return 0;
}