Cod sursa(job #3274492)

Utilizator SimifilLavrente Simion Simifil Data 6 februarie 2025 22:18:26
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
#include <deque>
using namespace std;
ifstream f ("deque.in");
ofstream g ("deque.out");

int main() {
	int n, k, sum = 0;
    f >> n >> k;
    deque<pair<int, int>> v;
    for( int i = 1; i < k; ++i )
    {
        pair<int, int> c;
        f >> c.first;
        c.second = i;

        while( v.empty() == false && v.front().second < i - k + 1 )
            v.pop_front();
        while( v.empty() == false && v.back().first > c.first )
            v.pop_back();
        v.push_back( c );

    }
    for( int i = k; i <= n; ++i )
    {
        pair<int, int> c;
        cin >> c.first;
        c.second = i;

        while( v.empty() == false && v.front().second < i - k + 1 )
            v.pop_front();
        while( v.empty() == false && v.back().first > c.first )
            v.pop_back();
        v.push_back( c );
        sum += v.front().first;
    }
    g << sum;
}