Cod sursa(job #2657229)

Utilizator AntoniuFicAntoniu Ficard AntoniuFic Data 10 octombrie 2020 09:58:09
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <deque>
#include <iostream>

using namespace std;

int n, k, v[5000000];

int main() {
    deque<int> D;
    int suma = 0;
    ifstream f("deque.in");
    ofstream g("deque.out");
    f>>n>>k;
    for (int i = 0; i < n; ++i) {
        f>>v[i];
    }
    D.push_back(0);
    for (int i = 1; i < k; ++i) {
        if(!D.empty() && v[D.back()] <= v[i]) D.push_back(i);
        else if(D.empty()) D.push_back(i);
        else{
            while(!D.empty() && v[D.back()] > v[i]) D.pop_back();
            D.push_back(i);
        }
    }
    for (int i = k; i < n; ++i) {
//        cout<<v[D.front()]<<endl;
        if(!D.empty()) suma += v[D.front()];
        while(!D.empty() && D.front() < i - k + 1) D.pop_front();
        if(!D.empty() && v[D.back()] <= v[i]) D.push_back(i);
        else if(D.empty()) D.push_back(i);
        else{
            while(!D.empty() && v[D.back()] > v[i]) D.pop_back();
            D.push_back(i);
        }
    }
//    cout<<v[D.front()];
    suma += v[D.front()];
    g<<suma;
    return 0;
}