Cod sursa(job #1752007)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 2 septembrie 2016 15:34:18
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <deque>
#define ff first
#define ss second

using namespace std;

deque< pair<int, int> > v;
int n, k;

int solve();
void write();

int main(){
    write();
    return 0;
}

int solve(){
    ifstream fin ("deque.in");
    int x, s(0);
    fin >> n >> k >> x;
    v.push_back(make_pair(x, 0));
    for (int i = 1; i < n; ++i){
        if (i - v.front().ss == k)
            v.pop_front();
        fin >> x;

        if (x > v.back().ff)
            v.push_back(make_pair(x, i));
        else{
            while (!v.empty() && v.back().ff >= x)
                v.pop_back();
            v.push_back(make_pair(x, i));
        }
        if (i < k - 1)
            continue;
        s += v.front().ff;
    }
    return s;
}

void write(){
    ofstream fout ("deque.out");
    fout << solve();
    fout.close();
}