Cod sursa(job #2732477)
| Utilizator | Data | 28 martie 2021 23:17:19 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.47 kb |
#include<stdio.h>
#include <fstream>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int a[5000001],n,k;
int b[5000001], c[5000001];
int main(){
long long r=0;
int i,st,dr;
fin>>n>>k;
for(i=1;i<=n;i++)
fin>>a[i];
st=1;dr=0;
for(i=1;i<=n;++i)
{
while(dr>=st && a[i]<b[dr])--dr;
++dr;
c[dr]=i;
b[dr]=a[i];
if(c[st]<=i-k) st++;
if(i>=k) r+=b[st];
}
fout<<r;
return 0;
}
