Cod sursa(job #2897695)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 4 mai 2022 15:54:58
Problema Deque Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")

using namespace std;

class InParser{
private:
    FILE *fin;
    char *buff;
    int sp;
    char read_ch()
    {
        sp++;
        if(sp==4096)
        {
            sp=0;
            fread(buff,1,4096,fin);
        }
        return buff[sp];
    }
public:
    InParser(const char * nume)
    {
        fin = fopen(nume,"r");
        buff = new char[4096]();
        sp=4095;
    }
    InParser& operator >> (int & n)
    {
        char c;
        while(!isdigit(c=read_ch())&&c!='-');
        int sgn=1;
        if(c=='-')
        {
            sgn=-1;
            n=0;
        }
        else n=c-'0';
        while(isdigit(c = read_ch()))
              n = n * 10 + c - '0';
        n*=sgn;
        return *this;
    }


};


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

deque<int> q;

const int NMAX = 100;

int a[NMAX+5];

int i,j,n,k;

long long ans;

void solve()
{
    fin>>n>>k;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
        while(!q.empty()&&a[i]<=a[q.back()])q.pop_back();
        q.push_back(i);
        if(!q.empty()&&q.front()<=i-k)q.pop_front();
        if(i>=k)
            ans+=a[q.front()];
    }
    fout<<ans<<'\n';
}

signed main()
{
    solve();
    return 0;
}