Cod sursa(job #2682058)

Utilizator Bodo171Bogdan Pop Bodo171 Data 7 decembrie 2020 18:26:00
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.56 kb
#include <iostream>
#include <fstream>

using namespace std;
const int nmax=5*1000*1000+1;
int st[nmax],dr[nmax];
int main(){
    ifstream f("deque.in");
    ofstream g("deque.out");
    int n, k, x;
    long long ans = 0;
    f>>n>>k;
    for(int i=1; i<=n; i++){
        f>>x;
        st[i] = x;
        if(i%k!=1) st[i] = min(st[i],st[i-1]);
        dr[i] = x;
    }
    for(int i=n-1; i>=1; i--)
        if((i+1)%k!=1) dr[i] = min(dr[i+1],dr[i]);
    for(int i=k;i <=n; i++)
        ans+=1LL*min(dr[i-k+1],st[i]);
    g<<ans;
    return 0;
}