C++ 解法, 执行用时: 2402ms, 内存消耗: 5344K, 提交时间: 2022-05-01 11:54:23

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+5;
ll n, m, k;
ll ans=0,t;
ll a[N];//原数据
ll c[N];
ll f[N];
ll st[N];
inline void wqs(ll x) {
  int l = 0, r = 0;
  st[0]=f[0]=c[0]= 0;
  for(int i=1;i<=n;i++){//每个物体进行遍历
    for(;l<=r&&i-st[l]>m;l++);
      f[i]=f[st[l]]+a[i]-x;
      c[i]=c[st[l]]+1;
      for (;l<=r&&(f[i]<f[st[r]]||(f[i]==f[st[r]]&&c[i]<=c[st[r]]));)r--;
      st[++r] = i;
    }
    for(;l<=r&&st[l]<=n-m;l++);
    ans = f[st[l]];
    t=c[st[l]];
}
int main() {
    int tt;
    cin>>tt;
    while (tt--) {
        cin>>n>>m>>k;
        for (int i = 1; i <= n; i++) cin>>a[i];//输入数组
        ll l = 0, r =1e9, mid;
        while (l+1<r) {
            mid = (l + r) >> 1;
            wqs(mid);
            if (t <= k) l = mid;
            else r = mid;
        }
        wqs(l);
        cout<<ans+1ll*l*k<<endl;
  }
  return 0;
}