Cod sursa(job #2671430)

Utilizator cyg_mihaizMIHAI ZARAFIU cyg_mihaiz Data 12 noiembrie 2020 09:03:28
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <deque>
#include <utility>
using namespace std;
typedef long long ll;
deque<pair<int,int> > Q;
ifstream fin("deque.in");
ofstream fout("deque.out");
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    int n,i,x,k;
    ll 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;
    fin.close();
    fout.close();
    return 0;
}