簡単な問題から考える．
取り方 \(s \in 2^{N}\) を固定
\(t := sum(s)\) とおく． \(s\) に対する答えは， \(x-t \equiv 0 \ mod \ |s|\) のとき \(\frac{x-t}{|s|}\) となる． それ以外のときは不可能．
取った個数 \(k \in [1,N]\) を固定
これも同様． \(k = |s|\) となる \(s \in 2^{N}\) を考える． \(\frac{x-t}{k}\) を最小にしたいから， 和 \(t\) を最大にすればよい．
答えは \(max_{s \in 2^{N} \\ |s| = k \\ x-t \equiv 0 \ mod \ k} \frac{x-t}{k}. \)
本問
取った個数 \(k\) を全探索する．
\(dp^{k}_{i,j,r} := \) \(max_{s \in 2^{i} \\ |s| = j \\ t \equiv r \ mod \ k} sum(s) \).
ans = \(min_{k \in [1,N] \\ dp^{k}_{N,k,x} \geq 0 \\ dp^{k}_{N,k,x} \equiv 0 \ mod \ k} \frac{x- dp^{k}_{N,k,x}}{k}\)
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,x;
cin >> n >> x;
vll a(n); rep(i,n) { cin >> a[i]; }
ll ans = INFL;
rep1(k,n) {
vvll dp(k+1, vll(k, -INFL));
dp[0][0] = 0;
rep(i,n) {
drep(j,k){ // 使った個数
rep(r,k){
chmax(dp[j+1][(r+a[i])%k], dp[j][r] + a[i]);
}
}
}
ll s = dp[k][x%k];
if(s >= 0){
assert((x-s) % k == 0);
chmin(ans, (x - s) / k);
}
}
cout << ans << endl;
return 0;
}
