Cod sursa(job #2041670)
| Utilizator | Data | 17 octombrie 2017 18:04:49 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.58 kb |
#include <iostream>
#include <cstdio>
#include <deque>
#define mx 5000001
using namespace std;
deque < pair<int,int> > coada;
int a[mx],k,suma;
int main (){
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int i,n,x;
cin>>n>>k;
for (i=0; i<n; i++){
cin>>x;
while ((!coada.empty()) && (x<coada.back().first))
coada.pop_back();
coada.push_back({x,i});
if (coada.front().second <= i-k) coada.pop_front();
if (i >= k-1) suma+=coada.front().first;
}
cout<<suma;
return 0;
}
