Cod sursa(job #2888730)

Utilizator AntoniaPopoviciAntonia-Adelina Popovici AntoniaPopovici Data 11 aprilie 2022 19:42:35
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <deque>
using namespace std;

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

deque <long long> minim;
long long v[5000001];
int main()
{
    
    long long n, k;
    long long rez = 0;
    fin >> n >> k;
    long long i, j;
    for (i = 1; i <= n; ++i)
    {
        fin >> v[i];
    
      while (!minim.empty() && v[minim.back()] >= v[i])
            minim.pop_back();

        minim.push_back(i);

        if (!minim.empty() && minim.front() == i - k)
            minim.pop_front();
        
        if (i >= k)
        {
            long long x = v[minim.front()];
            rez += x;
        }
    }
    fout << rez;
    return 0; 
}