T0485 彩色弹珠2

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<long long> d(n);
    vector<int> c(n);
    for (int i = 0; i < n; ++i) cin >> d[i];
    for (int i = 0; i < n; ++i) cin >> c[i];

    // 按颜色分组，每种颜色的弹珠按距离升序排列
    map<int, vector<long long>> groups;
    for (int i = 0; i < n; ++i) groups[c[i]].push_back(d[i]);
    for (auto &kv : groups) sort(kv.second.begin(), kv.second.end());

    const long long INF = (1LL << 62);
    // A[j]：取走 j 颗、每趟都往返的总代价
    // B[j]：取走 j 颗、最后一趟不回程的总代价（真正要的答案）
    vector<long long> A(k + 1, INF), B(k + 1, INF);
    A[0] = 0;
    B[0] = 0;

    for (auto &kv : groups) {
        const vector<long long> &g = kv.second;
        int sz = (int)g.size();
        // 沿用原状态表示「这种颜色一颗也不拿」
        vector<long long> nA = A, nB = B;
        for (int t = 1; t <= sz && t <= k; ++t) {
            long long e = g[t - 1]; // 这一趟的终点
            for (int j = 0; j + t <= k; ++j) {
                if (A[j] == INF) continue;
                nA[j + t] = min(nA[j + t], A[j] + 2 * e);
                nB[j + t] = min(nB[j + t], B[j] + 2 * e);
                nB[j + t] = min(nB[j + t], A[j] + e);
            }
        }
        A.swap(nA);
        B.swap(nB);
    }

    for (int j = 1; j <= k; ++j) cout << B[j] << (j == k ? '\n' : ' ');
    return 0;
}