Cod sursa(job #2712318)

Utilizator AdrianSkStanciu Adrian AdrianSk Data 25 februarie 2021 17:08:33
Problema Deque Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");

int v[5000001];
deque <int> interval;

int findTheMin(int k) {
    int mins = 10000000, temp = k;
    
    do {
        int aux = interval.front();
        interval.pop_front();
        mins = min(aux, mins);
        interval.push_back(aux);
    } while(--temp);
    
    return mins;
}

int main() {
    int n, k;
    fin >> n >> k;
    
    
    for(int i = 1; i <= n; ++i) {
        fin >> v[i];
        if(i <= k) {
           interval.push_back(v[i]);
        }
    }
    
    int sum = 0, temp = k;
    for(int i = k; i <= n; ++i) {
        if(temp < k) {
            interval.push_back(v[i]);
            temp = k;
        }
        sum += findTheMin(k);
        interval.pop_front();
        --temp; 
    }
    fout << sum;
}