F - Potion
[Q] https://atcoder.jp/contests/abc192/tasks/abc192_f
1. N=100と小さめ。O(N^4)でDPする。
2. DP[maxmod][index][mod] = maxval で管理。
maxmod は 1~N
index は 0~N
mod は 0~(N-1)
Q. DP[3][1][2] = 5 は？
A.
最終的に3個(maxmod)とる場合の探索だけど、
今は1個(index)とった時点。
その総和を3(maxmod)で割ったあまり val%3 == 2 を満たす最大の値が5だよ。という管理。
こんなシチュエーション。
A[] = {1,2,3,4,5}
3個とることを想定した探索で、
1個とった時点で3で割ったあまりが 2 になる最大の取り方は 5 // DP[3][1][2]Q. DPの値をデバッグ？
Q. 例1
3 9999999999
3 6 8
・1個とる場合
DP[1][0][0]:0 // 初期条件
DP[1][1][0]:8 // ★1個とる場合の最大値
9999999999%1 = 0 なので、 DP[1][1][0] が解答候補。
・2個とる場合
DP[2][0][0]:0 // 初期条件
DP[2][0][1]:0 // 初期条件
DP[2][1][0]:8 // 1個とるうち、val%2=0 になる最大値
DP[2][1][1]:3 // val%2=1
DP[2][2][0]:14 // 2個とるうち、val%2=0 になる最大値
DP[2][2][1]:11 // ★2個とる場合の最大値
9999999999%2 = 1 なので、 DP[2][2][1] が解答候補。
DP[3][0][0]:0
DP[3][0][1]:0
DP[3][0][2]:0
DP[3][1][0]:6
DP[3][1][1]:0
DP[3][1][2]:8
DP[3][2][0]:9
DP[3][2][1]:0
DP[3][2][2]:14
DP[3][3][0]:0 // ★3個とる場合の最大値(0なので考慮外)
DP[3][3][1]:0
DP[3][3][2]:17
9999999999%3 = 0 なので、 DP[3][3][0] が解答候補。だけど、0なので見ない。
答えは
DP[2][2][1]:11 が最大値なので、
2個とって、11 のポーションを作る。
(9999999999-11)/2 = 4999999994実装
int main(){
cincout();
cin >> N >> X;
rep(i, N) cin >> A[i];
ll ans = oo;
rep(i, N){
ll a = A[i];
for(ll mod=1; mod<=N; ++mod){
for (ll j=min(i, mod-1); j>=0; --j){ // 今とったらj個とることになる
rep(k, mod){
if (DP[mod][j][k] == 0 && (j>0 || k>0) ) continue;
ll val = DP[mod][j][k] + a;
chmax(DP[mod][j+1][(k+a)%mod], val);
}
}
}
}
for(ll i=1; i<=N; ++i){
ll val = DP[i][i][X%i];
if (val == 0) continue;
chmin(ans, (X-val)/i);
}
cout << ans << endl;