NAC 2020 J

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

const int MX = 6000, N = 31;

int n, m, a, cnt[N];
vector<int> adj[MX][N];
bool chk[2][MX];
vector<int> ve;
vector<vector<int>> par;

struct trie {
    int ind;
    trie *ch[N];

    trie(int _ind = 0) : ind(_ind) {
        fill(ch, ch + N, nullptr);
    }

    trie *access(int u) {
        if (ch[u] == nullptr) {
            ch[u] = new trie();
        }
        return ch[u];
    }
} *rt = new trie();

void make_partition(int n, int cur, trie *nod = rt) {
    if (n == 0) {
        nod->ind = par.size();
        par.push_back(ve);
    }
    if (n < cur) {
        return;
    }
    ve.push_back(cur);
    make_partition(n - cur, cur, nod->access(cur));
    ve.pop_back();
    make_partition(n, cur + 1, nod);
}

void make_edge(vector<int> &pr, int x, int pos = 0, int cur = 0, int sum = 0) {
    if (sum > n / 2) {
        return;
    }
    if (pos == pr.size()) {
        trie *nod = rt;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                nod = nod->access(i);
            }
        }
        adj[x][sum].push_back(nod->ind);
        ve.clear();
    } else {
        cnt[cur]++; cnt[pr[pos] - cur]++;
        int nxt = (pos + 1 == pr.size() || pr[pos + 1] == pr[pos] ? cur : 0);
        make_edge(pr, x, pos + 1, nxt, sum + cur);
        cnt[cur]--; cnt[pr[pos] - cur]--;
        if (cur < pr[pos]) {
            make_edge(pr, x, pos, cur + 1, sum);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    make_partition(n, 1);
    for (int i = 0; i < par.size(); i++) {
        make_edge(par[i], i);
    }
    int cur = 1, prv = 0;
    chk[1][par.size() - 1] = true;
    for (int i = 0; i < m; i++) {
        swap(cur, prv);
        fill(chk[cur], chk[cur] + par.size(), false);
        cin >> a;
        a = min(a, n - a);
        for (int j = 0; j < par.size(); j++) {
            if (chk[prv][j]) {
                for (int &v : adj[j][a]) {
                    chk[cur][v] = true;
                }
            }
        }
    }
    int mx = 0;
    for (int i = 0; i < par.size(); i++) {
        if (chk[cur][i]) {
            int cnt = 0;
            for (int j = 0; j < par[i].size(); j++) {
                cnt += (par[i][j] == 1);
            }
            mx = max(mx, cnt);
        }
    }
    cout << mx << '\n';
}