Cod sursa(job #2232181)
Utilizator | Data | 17 august 2018 18:14:28 | |
---|---|---|---|
Problema | Deque | Scor | 25 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.63 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
deque <int> coada;
int n,k,s,x,mi=INT_MAX,v[5000005];
int main()
{
in >> n >> k;
for(int i=1; i<=n; i++)
{
in >> v[i];
}
for(int i=1; i<=n; i++)
{
while(!coada.empty() && v[i]<=v[coada.back()])
{
coada.pop_back();
}
coada.push_back(i);
if(coada.front()==i-k)
{
coada.pop_front();
}
if(coada.back()>=k)
{
s+=v[coada.front()];
}
}
out << s;
return 0;
}