Cod sursa(job #1847512)
| Utilizator | Data | 14 ianuarie 2017 18:06:52 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.61 kb |
#include <cstdio>
#include <queue>
using namespace std;
typedef pair <int, int> ii;
deque<ii>q;
int main()
{
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int x, n ,i , k;
long long s;
scanf("%d%d", &n, &k);
s = 0;
for(i = 1;i <= n;i++){
scanf("%d", &x);
while(!q.empty() && q.back().first >= x){
q.pop_back();
}
q.push_back(ii(x, i));
while(!q.empty() && i-q.front().second + 1 > k){
q.pop_front();
}
if(i >= k)
s += q.front().first;
}
printf("%lld", s);
return 0;
}
