Cod sursa(job #2208461)

Utilizator RaresLiscanLiscan Rares RaresLiscan Data 29 mai 2018 21:16:22
Problema Deque Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("deque.in");
ofstream fout ("deque.out");
int v[5000005];
deque <int> D;
void inserare (int i)
{
    if (D.empty()) D.push_back(i);
    else {
        while (D.size() && v[D.back()] >= v[i]) D.pop_back();
        D.push_back(i);
    }
}
int main()
{
    int n, k;
    fin >> n >> k;
    for (int i = 1; i <= n; i ++) fin >> v[i];
    int suma = 0;
    for (int i = 1; i <= k; i ++) inserare(i);
    suma += v[D.front()], D.pop_front();
    for (int i = k + 1; i <= n; i ++) {
        inserare(i);
        suma += v[D.front()];
        if (D.front() + k - 1 <= i) D.pop_front();
    }
    fout << suma;
    fin.close();
    fout.close();
    return 0;
}