Cod sursa(job #2671429)

Utilizator cyg_mihaizMIHAI ZARAFIU cyg_mihaiz Data 12 noiembrie 2020 09:01:34
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include <fstream>
#include <deque>
#include <utility>
using namespace std;
typedef long long ll;
deque<pair<ll,int> > Q;
ifstream fin("deque.in");
ofstream fout("deque.out");
int main()
{
    ll n,i,x,k,ans;
    fin>>n>>k;
    ans=0;
    for(i=1;i<=n;i++){
        fin>>x;
        while(!Q.empty() and Q.back().first>x)
            Q.pop_back();
        Q.push_back(make_pair(x,i));
        if(Q.front().second<=i-k)
            Q.pop_front();
        if(i>=k)
            ans=ans+Q.front().first;
    }
    fout<<ans;
    return 0;
}