Cod sursa(job #3171624)
Utilizator | Rebegea Stefan ReBeGhEl | Data | 19 noiembrie 2023 10:41:11 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
deque < pair < int , int > > dq;
int main()
{
int n,k,a;
long long s=0;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a;
if(!dq.empty()&&dq.front().second==i-k)
dq.pop_front();
while(!dq.empty()&&a<=dq.back().first)
dq.pop_back();
dq.push_back({a,i});
if(i>=k)
s+=dq.front().first;
}
cout<<s;
return 0;
}