結果

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

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 8016KB
2 AC 100% 2ms 8192KB
3 AC 100% 2ms 7632KB
4 AC 100% 2ms 8432KB
5 AC 100% 2ms 7248KB
6 AC 100% 2ms 7600KB
7 AC 100% 2ms 8416KB
8 AC 100% 2ms 8528KB
9 AC 100% 2ms 7872KB
10 AC 100% 2ms 7536KB
11 AC 100% 2ms 8464KB
12 AC 100% 2ms 7648KB
13 AC 100% 2ms 8224KB
14 AC 100% 2ms 8432KB
15 AC 100% 2ms 7888KB
16 AC 100% 1ms 8736KB
17 AC 100% 2ms 7264KB
18 AC 100% 2ms 8416KB
19 AC 100% 2ms 7888KB
20 AC 100% 2ms 8320KB
21 AC 100% 2ms 8752KB
22 AC 100% 3ms 7248KB
23 AC 100% 2ms 8464KB
24 AC 100% 4ms 8032KB
25 AC 100% 2ms 7536KB
26 AC 100% 3ms 8192KB
27 AC 100% 4ms 8176KB
28 AC 100% 2ms 8032KB
29 AC 100% 14ms 7264KB
30 AC 100% 3ms 8448KB

ソースコード

#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];
      }

      dp[mask+(1<<i)] = min(dp[mask+(1<<i)], dp[mask]+tmp);
    }
  }

  cout << dp[(1<<n)-1] << endl;
}