Cod sursa(job #1159854)
| Utilizator | Data | 29 martie 2014 22:09:20 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.62 kb |
#include <cstdio>
#include <deque>
using namespace std;
deque<int> Q;
int N,K,v[5000005];
long long mini;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&N,&K);
int x,pz = 0;
for(int i = 1; i <= N; ++i)
scanf("%d",&v[i]);
for(int i = 1; i <= N; ++i)
{
while(!Q.empty() && v[Q.back()] > v[i])
Q.pop_back();
Q.push_back(i);
if( Q.front() <= i - K )
Q.pop_front();
if(i >= K)
mini += v[Q.front()];
}
printf("%lld\n",mini);
return 0;
}
