結果

提出番号 2190
提出者 toof
言語 C++
提出日時 2018-12-06 21:28:15
問題名 (70)アルゴリズムのお勉強
結果 AC
点数 100%

テストケース

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define FOR(i, m, n) for(ll i = m;i < n;i++)

int main() {
  cin.tie(0); ios::sync_with_stdio(false);

  int n;
  cin >> n;
  vector<int> t(n);
  rep(i, n) cin >> t[i];
  vector<vector<int>> a(n, vector<int>(n));
  rep(i, n) rep(j, n) cin >> a[i][j];

  int dp[1<<16];
  rep(i, 1<<n) dp[i] = 1000*16+100;
  dp[0] = 0;

  rep(mask, 1<<n) {
    rep(i, n) {
      if (mask & 1<<i) continue;

      int tmp = t[i];
      rep(j, n) {
        if (mask & 1 << j) tmp -= a[j][i];
      }

      cerr << bitset<3>(mask) << endl;
      cerr << bitset<3>(mask+1<<i);
      dp[mask+(1<<i)] = min(dp[mask+(1<<i)], dp[mask]+tmp);
    }
  }

  cerr << endl;
  rep(i, 1<<n) {
    cerr << bitset<3>(i) << endl;
    cerr << dp[i] << endl;
  }
  cerr << (1<<n)-1 << endl;
  cout << dp[(1<<n)-1] << endl;
}