Cod sursa(job #579104)
| Utilizator | Data | 11 aprilie 2011 20:55:27 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.51 kb |
#include<cstdio>
#include<queue>
#define Nmax 5000001
using namespace std;
int N,K,v[Nmax];
deque <int> a;
long long sol;
int main(){
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&N,&K);
for(int i=1;i<=N;++i){
scanf("%d",&v[i]);
while(!a.empty() && v[i] < v[a.back()])
a.pop_back();
a.push_back(i);
if(i-a.front() >=K )
a.pop_front();
if(i>=K)
sol+=v[a.front()];
}
printf("%lld\n",sol);
return 0;
}
