Submission #3611312

---

Source Code Expand

#include <deque>
#include <iostream>
using namespace std;

const int N = 1e5;
int a[N + 1];

int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  a[n] = 0;
  ++n;
  int water = 0;
  int last = 0;
  deque<int> q;
  long long res = 0;
  for (int u = 0; u < n; ++u) {
    while (!q.empty() && q.front() < u) {
      q.pop_front();
    }
    while (water < k) {
      while (last <= u + water && last < n) {
        while (!q.empty() && a[last] <= a[q.back()]) {
          q.pop_back();
        }
        q.push_back(last);
        ++last;
      }
      res += a[q.front()];
      ++water;
    }
    --water;
  }
  cout << res << '\n';
  return 0;
}

Submission Info

Judge Result