Cod sursa(job #1847482)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 14 ianuarie 2017 17:41:02
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#include <queue>
 
using namespace std;
const int MAX_N = 5000000;
 
typedef pair <int, int> ii;
 
int v[MAX_N];
deque <ii> q;
 
int main() {
  freopen ("deque.in", "r", stdin);
  freopen ("deque.out", "w", stdout);
   
  int N, k;
  scanf ("%d%d", &N, &k);
   
  for (int i = 1; i <= N; ++i) {
    scanf ("%d", &v[i]);
  }
  long long s = 0;
  for (int i = 1; i <= N; ++i) {
    while (!q.empty() && v[i] <= q.back().first) {
      q.pop_back();
    }
    q.push_back (ii (v[i], i));
    if (i >= k) {
      while (!q.empty() && i - q.front().second + 1 > k) {
        q.pop_front();
      }
      s += q.front().first;
    }
  }
   
  printf ("%lld\n", s);
  return 0;
}