提出 #73227624

---

ソースコード 拡げる

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

int N, M;
vector<long long> W, C, remC;
vector<long long> suffixW; // suffixW[i] = sum_{k=i..N-1} W[k]

bool dfs(int i, long long remSum) {
    if (i == N) return true;

    // 减枝 1：剩余总容量 < 剩余总重量 => 不可能
    if (remSum < suffixW[i]) return false;

    long long w = W[i];

    // 减枝 2：如果当前包裹放不进任何车，直接失败
    bool anyFit = false;
    for (int j = 0; j < M; j++) {
        if (remC[j] >= w) { anyFit = true; break; }
    }
    if (!anyFit) return false;

    // 减枝 3：同层对称性（相同剩余容量的车只试一次）
    unordered_set<long long> seen;
    seen.reserve(M * 2);

    for (int j = 0; j < M; j++) {
        if (remC[j] < w) continue;
        if (seen.count(remC[j])) continue;
        seen.insert(remC[j]);

        remC[j] -= w;
        if (dfs(i + 1, remSum - w)) return true;
        remC[j] += w;
    }
    return false;
}

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

    cin >> N >> M;
    W.resize(N);
    C.resize(M);
    for (int i = 0; i < N; i++) cin >> W[i];
    for (int j = 0; j < M; j++) cin >> C[j];

    // 大件先放，减枝更强
    sort(W.begin(), W.end(), greater<long long>());
    // 容量排序不影响可行性判断（只是帮助更快剪枝）
    sort(C.begin(), C.end(), greater<long long>());

    remC = C;

    // 预处理 suffixW
    suffixW.assign(N + 1, 0);
    for (int i = N - 1; i >= 0; i--) suffixW[i] = suffixW[i + 1] + W[i];

    long long totalCap = 0;
    for (auto x : C) totalCap += x;

    bool ok = dfs(0, totalCap);
    cout << (ok ? "Yes\n" : "No\n");
    return 0;
}

提出情報

ジャッジ結果