从loj跑来问

// Time: 2023-07-16 00:30:23
// Problem: #10177. 「一本通 5.5 例 3」修剪草坪
// Contest: LibreOJ
// URL: https://loj.ac/p/10177
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Author: Zhong Jiaxuan
// Luogu: 637788
// Email: zhongjiaxuankimi@qq.com
// Tips:
//   - INT_MAX = 2147483647
//   - INT_MIN = -2147483648
// Tag:
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
#define db double
using namespace std;
int n, k;
vector<int> arr, sum;
vector<int> dp1, dp2;
deque<int> de;
signed main() {

  cin >> n >> k;
  arr.resize(n);
  dp1.resize(n);
  dp2.resize(n);
  for (int &i : arr)
    cin >> i;
  sum.push_back(arr[0]);
  for (int i = 1; i < n; i++)
    sum.push_back(sum[i - 1] + arr[i]);
  for (int i = 0; i < n; i++) {
    if (i == 0)
      dp1[i] = 0;
    else
      dp1[i] = max(dp1[i - 1], dp2[i - 1]);
    while (de.size() && de.front() < i - k)
      de.pop_front();
    dp2[i] = sum[i] + (de.size() ? dp1[de.front()] - sum[de.front()] : 0);
    while (de.size() && dp1[de.back()] - sum[de.back()] <= dp1[i] - sum[i])
      de.pop_back();
    de.push_back(i);
  }
  for (int i : dp1)
    cout << i << ' ';
  cout << endl;
  for (int i : dp2)
    cout << i << ' ';
  cout << endl;
  cout << max(dp1[n - 1], dp2[n - 1]);
  return 0;
}