結果

提出番号 2222
提出者 syawacha
言語 C++
提出日時 2019-04-05 17:11:43
問題名 (70)アルゴリズムのお勉強
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 8192KB
2 AC 100% 2ms 7840KB
3 AC 100% 2ms 8176KB
4 AC 100% 2ms 8480KB
5 AC 100% 2ms 8480KB
6 AC 100% 2ms 8176KB
7 AC 100% 2ms 7872KB
8 AC 100% 2ms 8320KB
9 AC 100% 2ms 7856KB
10 AC 100% 2ms 8112KB
11 AC 100% 2ms 8528KB
12 AC 100% 2ms 7872KB
13 AC 100% 2ms 8512KB
14 AC 100% 2ms 8336KB
15 AC 100% 2ms 7840KB
16 AC 100% 2ms 7856KB
17 AC 100% 2ms 8112KB
18 AC 100% 2ms 8112KB
19 AC 100% 2ms 8432KB
20 AC 100% 2ms 8592KB
21 AC 100% 2ms 7840KB
22 AC 100% 3ms 8096KB
23 AC 100% 2ms 7952KB
24 AC 100% 4ms 8480KB
25 AC 100% 2ms 7872KB
26 AC 100% 3ms 8144KB
27 AC 100% 4ms 7856KB
28 AC 100% 2ms 8096KB
29 AC 100% 13ms 8144KB
30 AC 100% 3ms 8528KB

ソースコード

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

const int inf = 1000000000;

int main(){
  int N;
  cin >> N;
  int t[N];
  for(int i=0;i<N;i++) cin >> t[i];
  int a[N][N];
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      cin >> a[i][j];
    }
  }

  int dp[1 << N];
  fill(dp,dp+(1<<N),inf);
  dp[0] = 0;
  for(int i=0;i<(1<<N);i++){
    for(int j=0;j<N;j++){
      if(!(i & (1 << j))){
        int dt = 0;
        for(int k=0;k<N;k++){
          if(i & (1 << k)){
            dt += a[k][j];
          }
        }
        dp[i + (1 << j)] = min(dp[i + (1 << j)], dp[i] + t[j] - dt);
      }
    }
  }

  cout << dp[(1 << N) - 1] << endl;
  return 0;
}