Cod sursa(job #1847512)

Utilizator mateicosCostescu Matei mateicos 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;
}