Omiyage [yukicoder 914]

https://yukicoder.me/problems/no/914

前提知識

• 動的計画法(yes/no)

解説

https://yukicoder.me/submissions/393060

やりすぎ感があるが、DPしよう。
dp[i][k] := 国iまでお土産を買っていて、残りの金額がkである場合があるか

int N, M, K, A[10][10];
bool dp[11][501];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, N) rep(j, 0, M) cin >> A[i][j];

    rep(i, 0, N + 1) rep(k, 0, K + 1) dp[i][k] = false;
    dp[0][K] = true;
    rep(i, 0, N) rep(k, 0, K + 1) rep(j, 0, M) {
        if(0 <= k - A[i][j]) dp[i + 1][k - A[i][j]] |= dp[i][k];
    }

    int ans = K;
    rep(k, 0, K + 1) if (dp[N][k]) chmin(ans, k);
    if (ans == K) ans = -1;
    cout << ans << endl;
}