Cod sursa(job #2682058)
Utilizator | Bogdan 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;
}