Cod sursa(job #2112672)

Utilizator omegasFilip Ion omegas Data 23 ianuarie 2018 19:09:50
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>

#define maxn 5000001

using namespace std;

ifstream fin("deque.in");
ofstream fout("deque.out");

int l = 1,r = 0;
int dq[maxn];
int v[maxn];
long long sum;

void push(int a){
    ++r;
    dq[r] = a;
}

void print(){
 int i;
 for(i=l;i<=r;++i)
    cout << dq[i] << ' ';
 cout << endl;
}



int main()
{
    int n,k,t;
    fin >> n >> k;
    for(t=1;t<=n;++t){
        fin >> v[t];

        if(t >= k + 1)
            sum += v[dq[l]];


        while(r >= l && v[t] < v[dq[r]])
            --r;

        push(t);



        if(dq[l] + k  <= t)
            ++l;

    }
    sum += v[dq[l]];
    fout << sum;

    return 0;
}