結果

提出番号 2243
提出者 taotao54321
言語 C++
提出日時 2019-08-19 03:58:59
問題名 (70)アルゴリズムのお勉強
結果 CE
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 CE 0% 0ms 0KB
2 CE 0% 0ms 0KB
3 CE 0% 0ms 0KB
4 CE 0% 0ms 0KB
5 CE 0% 0ms 0KB
6 CE 0% 0ms 0KB
7 CE 0% 0ms 0KB
8 CE 0% 0ms 0KB
9 CE 0% 0ms 0KB
10 CE 0% 0ms 0KB
11 CE 0% 0ms 0KB
12 CE 0% 0ms 0KB
13 CE 0% 0ms 0KB
14 CE 0% 0ms 0KB
15 CE 0% 0ms 0KB
16 CE 0% 0ms 0KB
17 CE 0% 0ms 0KB
18 CE 0% 0ms 0KB
19 CE 0% 0ms 0KB
20 CE 0% 0ms 0KB
21 CE 0% 0ms 0KB
22 CE 0% 0ms 0KB
23 CE 0% 0ms 0KB
24 CE 0% 0ms 0KB
25 CE 0% 0ms 0KB
26 CE 0% 0ms 0KB
27 CE 0% 0ms 0KB
28 CE 0% 0ms 0KB
29 CE 0% 0ms 0KB
30 CE 0% 0ms 0KB

ソースコード

/**
 * 
 */

#include <iostream>
#include <vector>
#include <cstdint>
using namespace std;

using i64 = int64_t;

constexpr i64 INF  = INT64_C(1'010'000'000'000'000'017);

#define FOR(i, start, end) for(i64 i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)

template<typename T, typename U, typename Comp=less<>>
constexpr bool chmin(T& xmin, const U& x, Comp comp={}) noexcept {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

//--------------------------------------------------------------------

void solve() {
    i64 N; cin >> N;

    vector<i64> T(N);
    REP(i, N) { cin >> T[i]; }

    vector<vector<i64>> M(N, vector<i64>(N));
    REP(i, N) REP(j, N) {
        cin >> M[i][j];
    }

    vector<i64> dp(1LL<<N, INF);
    dp[0] = 0;

    REP(i, 1LL<<N) {
        REP(j, N) {
            if(i&(1LL<<j)) continue;
            i64 t = T[j];
            REP(k, N) {
                if(i&(1LL<<k))
                    t -= M[k][j];
            }
            chmin(dp[i|(1LL<<j)], t+dp[i]);
        }
    }

    i64 ans = dp[(1LL<<N)-1];

    cout << ans << "\n";
}

signed main() {
    

    solve();

    return 0;
}