Cod sursa(job #2127687)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 10 februarie 2018 22:12:27
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.5 kb
#include <bits/stdc++.h>
using namespace std;
deque <int> Q;
long long n, k, i, s, v[5000005];
int main()
{
    ifstream f("deque.in");
    ofstream g("deque.out");
    f >> n >> k;
    for(i = 1;i <= n;i++)
        f >> v[i];
    Q.push_back(1);
    for(i = 2;i <= n;i++)
    {
        while(!Q.empty() && v[Q.back()] > v[i])Q.pop_back();
        Q.push_back(i);
        if(Q.back() - Q.front() >= k)Q.pop_front();
        if(i >= k)s = s + v[Q.front()];
    }
    g << s;
    return 0;
}