Cod sursa(job #1672006)
Utilizator | Data | 2 aprilie 2016 12:12:32 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
deque<int> mi;
int a[5000101],n,k;
long long s;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
while(!mi.empty()&&a[mi.front()]>=a[i])
mi.pop_front();
mi.push_front(i);
if(mi.back()==i-k) {mi.pop_back();}
if(i>=k) s=s+a[mi.back()];
}
cout<<s;
return 0;
}