题目是 CF gym 100886 A

Wrong answer on test 17

求 Hack，悬赏关注。

#include <iostream>
#include <cstring>
using namespace std;
int n, x[410], cnt[40], dp[4010][4040], ans = 1000000000, sum, g[4010][4040], ansa, ansb, f[410][12010], op[410], cntop, ansc;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i];
        cnt[x[i]]++;
        sum += x[i];
    }
    dp[0][0] = 1;
    for(int i = 1; i <= 30; i++) {
        for(int a = 0; a <= 4000; a++) {
            for(int b = 0; b <= 4030; b++) {
                if (dp[a][b]) {
                    g[a][b] = 0;
                } else {
                    g[a][b] = min((a >= i ? g[a - i][b] : 500), (b >= i ? g[a][b - i] : 500)) + 1;
                }
            }
        }
        for(int a = 0; a <= 4000; a++) {
            for(int b = 0; b <= 4030; b++) {
                dp[a][b] = (g[a][b] <= cnt[i]);
                if (i == 30 && dp[a][b]) {
                    if (max(sum - a - b, max(a, b)) - min(sum - a - b, min(a, b)) < ans) {
                        ans = max(sum - a - b, max(a, b)) - min(sum - a - b, min(a, b));
                        ansa = a;
                        ansb = b;
                    }
                }
            }
        }
    }
    ansc = sum - ansa - ansb;
    cout << ans << endl;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= ansa; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= x[i]) {
                f[i][j] |= f[i - 1][j - x[i]];
            }
        }
    }
    for(int i = n; i; i--) {
        if (f[i][ansa] == f[i - 1][ansa - x[i]]) {
            op[++cntop] = i;
            ansa -= x[i];
            x[i] = -1;
        }
    }
    cout << cntop << (cntop ? ' ' : '\n');
    for(int i = 1; i <= cntop; i++) {
        cout << op[i] << (i == cntop ? '\n' : ' ');
    }
    memset(f, 0, sizeof(f));
    cntop = 0;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= ansb; j++) {
            f[i][j] = f[i - 1][j];
            if (x[i] != -1 && j >= x[i]) {
                f[i][j] |= f[i - 1][j - x[i]];
            }
        }
    }
    for(int i = n; i; i--) {
        if (x[i] != -1 && f[i][ansb] == f[i - 1][ansb - x[i]]) {
            op[++cntop] = i;
            ansb -= x[i];
            x[i] = -1;
        }
    }
    cout << cntop << (cntop ? ' ' : '\n');
    for(int i = 1; i <= cntop; i++) {
        cout << op[i] << (i == cntop ? '\n' : ' ');
    }
    memset(f, 0, sizeof(f));
    cntop = 0;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= ansc; j++) {
            f[i][j] = f[i - 1][j];
            if (x[i] != -1 && j >= x[i]) {
                f[i][j] |= f[i - 1][j - x[i]];
            }
        }
    }
    for(int i = n; i; i--) {
        if (x[i] != -1 && f[i][ansc] == f[i - 1][ansc - x[i]]) {
            op[++cntop] = i;
            ansc -= x[i];
        }
    }
    cout << cntop << (cntop ? ' ' : '\n');
    for(int i = 1; i <= cntop; i++) {
        cout << op[i] << (i == cntop ? '\n' : ' ');
    }
    return 0;
}