結果

提出番号 2245
提出者 taotao54321
言語 C++
提出日時 2019-08-19 04:03:22
問題名 (70)アルゴリズムのお勉強
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 7904KB
2 AC 100% 2ms 8224KB
3 AC 100% 2ms 7552KB
4 AC 100% 2ms 7840KB
5 AC 100% 2ms 7824KB
6 AC 100% 2ms 8672KB
7 AC 100% 2ms 8432KB
8 AC 100% 2ms 7840KB
9 AC 100% 2ms 7568KB
10 AC 100% 2ms 8688KB
11 AC 100% 2ms 8176KB
12 AC 100% 2ms 8656KB
13 AC 100% 2ms 7824KB
14 AC 100% 2ms 7840KB
15 AC 100% 2ms 7840KB
16 AC 100% 2ms 7936KB
17 AC 100% 2ms 7664KB
18 AC 100% 2ms 8688KB
19 AC 100% 2ms 8640KB
20 AC 100% 2ms 8096KB
21 AC 100% 2ms 7856KB
22 AC 100% 3ms 8320KB
23 AC 100% 2ms 8448KB
24 AC 100% 4ms 8656KB
25 AC 100% 2ms 8672KB
26 AC 100% 3ms 8192KB
27 AC 100% 4ms 8560KB
28 AC 100% 2ms 7664KB
29 AC 100% 12ms 7856KB
30 AC 100% 3ms 7936KB

ソースコード

/**
 * 
 */

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

const long long INF = 1010000000000000017LL;

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

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

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

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

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

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

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

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

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

signed main() {
    

    solve();

    return 0;
}