Cod sursa(job #1516776)
Utilizator | Data | 3 noiembrie 2015 16:10:48 | |
---|---|---|---|
Problema | Deque | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <bits/stdc++.h>
using namespace std;
long long n,k,i,ma,df,v[5000010],mi,s;
deque<long long>dm;
int main()
{
freopen("deque.in","r",stdin);
ofstream g ("deque.out");
scanf("%lld%lld",&n,&k);
for(i=1; i<=n; ++i)
scanf("%lld",&v[i]);
mi=10000001;
for(i=1; i<=n; ++i)
{
while(!dm.empty()&&v[i]<v[dm.back()])dm.pop_back();
dm.push_back(i);
if(i-dm.front()==k)dm.pop_front();
if(i>=k)s+=1LL*v[dm.front()];
}
g<<s;
return 0;
}