WA 20 个求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 2e5 + 5;
int n = mread(), k = mread(), a[N], s[N];
int query(int l, int r){
    return s[r] - s[l - 1];
}
vector<vector<vector<int> > > dfs(int l, int r){
    int len = r - l + 1, mid = l + r >> 1;
    vector<vector<vector<int> > > f(len / k + 5, vector<vector<int> >(k, vector<int>(k, -0x3f3f3f3f3f3f3f3f)));
    for(int i = 0; i < k; i ++){
        for(int j = 0; j < k; j ++){
            f[0][i][j] = 0;
        }
    }
    if(len <= k + k){
        if(len == k + k){
            f[2][0][0] = query(l, l + k - 1) + query(r - k + 1, r);
        }
        for(int j = l; j <= r - k + 1; j ++){
            for(int s1 = 0; s1 < k && s1 <= j - l; s1 ++){
                for(int s2 = 0; s2 < k && s2 <= r - (j + k - 1); s2 ++){
                    f[1][s1][s2] = max(f[1][s1][s2], query(j, j + k - 1));
                }
            }
        }
        return f;
    }
    int lenl = mid - l + 1, lenr = r - (mid + 1) + 1;
    auto fl = dfs(l, mid), fr = dfs(mid + 1, r);

    vector<int> d;
    for(int i = 0; i < k; i ++){
        for(int j = 0; j < k; j ++){
            for(int s1 = 1; s1 <= lenl / k; s1 ++){
                d.push_back(fl[s1][i][0] - fl[s1 - 1][i][0]);
            }
            for(int s2 = 1; s2 <= lenr / k; s2 ++){
                d.push_back(fr[s2][0][j] - fr[s2 - 1][0][j]);
            }
            sort(d.begin(), d.end(), [](int a, int b){
                return a > b;
            });
            int sum = 0;
            for(int s = 1; s <= lenl / k + lenr / k; s ++){
                sum += d[s - 1];
                f[s][i][j] = sum;
            }
            d.clear();
            // for(int s1 = 0; s1 <= lenl / k; s1 ++){
            //     for(int s2 = 0; s2 <= lenr / k; s2 ++){
            //         f[s1 + s2][i][j] = max(f[s1 + s2][i][j], fl[s1][i][0] + fr[s2][0][j]);
            //     }
            // }
        }
    }

    for(int i = 0; i < k; i ++){
        for(int j = 0; j < k; j ++){
            // 左边留 i 个，右面留 j 个
            for(int ml = 1; ml < k; ml ++){
                if(i + ml <= lenl && j + (k - ml) <= lenr){
                    for(int s1 = 1; s1 <= lenl / k; s1 ++){
                        d.push_back(fl[s1][i][ml] - fl[s1 - 1][i][ml]);
                    }
                    for(int s2 = 1; s2 <= lenr / k; s2 ++){
                        d.push_back(fr[s2][k - ml][j] - fr[s2 - 1][k - ml][j]);
                    }
                    sort(d.begin(), d.end(), [](int a, int b){
                        return a > b;
                    });
                    f[1][i][j] = max(f[1][i][j], query(mid - ml + 1, mid + 1 + k - ml - 1));
                    int sum = 0;
                    for(int s = 1; s <= lenl / k + lenr / k; s ++){
                        sum += d[s - 1];
                        f[s + 1][i][j] = max(f[s + 1][i][j], sum + query(mid - ml + 1, mid + 1 + k - ml - 1));
                    }
                    d.clear();
                    // for(int s1 = 0; s1 <= lenl / k; s1 ++){
                    //     for(int s2 = 0; s2 <= lenr / k; s2 ++){
                    //         f[s1 + s2 + 1][i][j] = max(f[s1 + s2 + 1][i][j], fl[s1][i][ml] + fr[s2][k - ml][j] + query(mid - ml + 1, mid + 1 + k - ml - 1));
                    //     }
                    // }
                }
            }
        }
    }
    return f;
}
signed main(){
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    auto ans = dfs(1, n);
    for(int i = 1; i <= n / k; i ++){
        printf("%lld ", ans[i][0][0]);
    }
    return 0;
}