Cod sursa(job #3217084)

Utilizator BoggiGurau Bogdan Boggi Data 20 martie 2024 22:49:56
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <deque>
using namespace std;

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

#define PI pair<int, int>
#define DQP deque<PI>

int main() {
    int N, K;
    fin >> N >> K;
    DQP alegeri;
    long long suma = 0;
    for (int i = 0; i < N; ++i) {
        int no;
        fin >> no;
        while (!alegeri.empty() && alegeri.back().first > no) {
            alegeri.pop_back();
        }
        alegeri.push_back(make_pair(no, i + 1));
        if (alegeri.front().second <= i - K + 1) {
            alegeri.pop_front();
        }
        if (i >= K - 1)
            suma += alegeri.front().first;
    }
    fout << suma;
}