結果
問題 |
No.943 取り調べ
|
ユーザー |
|
提出日時 | 2020-12-19 14:34:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 182 ms / 1,206 ms |
コード長 | 958 bytes |
コンパイル時間 | 2,040 ms |
コンパイル使用メモリ | 198,896 KB |
最終ジャッジ日時 | 2025-01-17 03:50:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); int N; { cin >> N; } vector<vector<int>> X(N, vector<int>(N)); { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cin >> X[i][j]; } } } vector<int> A(N); { for (int i = 0; i < N; ++i) { cin >> A[i]; } } vector<int> masks(N); { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { masks[i] |= X[i][j] << j; } } } int res = accumulate(A.begin(), A.end(), 0); for (int s = 0; s < 1 << N; ++s) { int cost = 0; { for (int i = 0; i < N; ++i) if (s >> i & 1) { cost += A[i]; } } int t = s; { for (int _ = 0; _ < N; ++_) { for (int i = 0; i < N; ++i) { if ((masks[i] & t) == masks[i]) t |= 1 << i; } } } if (t == (1 << N) - 1) res = min(res, cost); } cout << res << endl; }