Submission #37169694

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, M, K;
  cin >> N >> M >> K;
  vector<int64_t> A(N);
  for (int n = 0; n < N; ++n) {
    cin >> A[n];
  }

  vector<int64_t> sorted(M);
  for (int m = 0; m < M; ++m) {
    sorted[m] = A[m];
  }
  sort(sorted.begin(), sorted.end());
  int64_t ans = accumulate(sorted.begin(), sorted.begin() + K, 0LL);
  cout << ans;
  for (int i = 0; i + M < N; ++i) {
    auto it = lower_bound(sorted.begin(), sorted.end(), A[i+M]);
    if (distance(sorted.begin(), it) < K) {
      ans += A[i+M];
      ans -= *(sorted.begin() + K - 1);
    }
    sorted.insert(it, A[i+M]);

    it = lower_bound(sorted.begin(), sorted.end(), A[i]);
    if (distance(sorted.begin(), it) < K) {
      ans -= A[i];
      ans += *(sorted.begin() + K);
    }
    sorted.erase(it);
    cout << " " << ans;
  }
  cout << endl;
}

Submission Info

Judge Result