Cod sursa(job #3126704)
Utilizator | Tudor Chitu TediCutu | Data | 6 mai 2023 21:28:30 |
---|---|---|---|
Problema | Deque | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include<bits/stdc++.h>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
long long n, k, st, dr=-1, sol;
int main()
{
fin>>n>>k;
vector<long long> v(n);
vector<long long> poz(n);
for(long long i = 0; i < n; i++)
{
fin>>v[i];
while(st<=dr && v[i]<=v[poz[dr]]) dr--;
dr++;
poz[dr]=i;
if(poz[st]==poz[dr]-k)
st++;
if(poz[dr]+1>=k)
sol+=v[poz[st]];
}
fout<<sol;
return 0;
}