Cod sursa(job #2050729)

Utilizator theo2003Theodor Negrescu theo2003 Data 28 octombrie 2017 11:08:34
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <algorithm>
#include <fstream>
#include <vector>

int main(){
    int n, k;
    std::ifstream in("deque.in");
    long long int result = 0;
    in>>n>>k;
    std::vector<int> last(k, 0);
    bool last_used = false;
    in>>last[0];
    int min = last[0];
    for(int x = 1;x<k;x++){
        in>>last[x];
        min = std::min(min, last[x]);
        last_used = (min==last[0])&&(last[0]!=last[x]);
    }
    result+=*std::min_element(last.begin(), last.end());
    int tail_ptr = 0, last_tail;
    for(int x = k;x<n;x++){
        last_tail = tail_ptr;
        in>>last[tail_ptr];
        tail_ptr++;
        if(tail_ptr==k)tail_ptr = 0;
        if(last_used){
            min = *std::min_element(last.begin(), last.end());
        }else{
            min = std::min(min, last[last_tail]);
        }
        last_used = (last[tail_ptr]==min)&&(last[tail_ptr]!=last[last_tail]);
        result+=min;
    }
    std::ofstream("deque.out")<<result;
}