結果
問題 | No.943 取り調べ |
ユーザー |
|
提出日時 | 2019-12-15 02:30:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 1,206 ms |
コード長 | 1,712 bytes |
コンパイル時間 | 1,621 ms |
コンパイル使用メモリ | 171,192 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 11:21:55 |
合計ジャッジ時間 | 2,895 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
//confilm 0LL and 1LL //confilm cornercase such as 0 #include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<ll, ll>; using Vec = vector<ll>; using VecP = vector<P>; using VecB = vector<bool>; #define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i)) #define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i)) #define REPR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i)) #define rep(i, n) REP(i, 0, n) #define repn(i, n) REPN(i, 1, n) #define repr(i, n) REPR(i, n, 0) #define repnr(i, n) REPR(i, n, 1) #define co(n) cout << (n) << endl #define cosp(n) cout << (n) << ' ' #define setp(n) cout << fixed << setprecision(n); #define all(s) (s).begin(), (s).end() #define pb push_back #define mp make_pair #define mt make_tuple #define fs first #define sc second template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b; return true;} return false;} template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b; return true;} return false;} const ll INF = 1e9+1; const ll LINF = 1e18+1; const ll MOD = 1e9+7; //const ll MOD = 998244353; const double PI = acos(-1); const double EPS = 1e-9; int main(void){ ll n; cin >> n; vector<bitset<18> > b(n); rep(i, n) rep(j, n){ ll f; cin >> f; b[i][j] = f; } Vec a(n); rep(i, n) cin >> a[i]; ll ans = LINF; rep(bit, (1 << n)){ bool flg = true; bitset<18> bits(bit), conf(0); while(flg){ flg = false; rep(i, n){ if(!conf[i] && ((conf|bits)&b[i]) == b[i]){ conf[i] = 1; flg = true; } } } if(conf.count() == n){ ll sum = 0; rep(i, n) if(bits[i]) sum += a[i]; chmin(ans, sum); } } co(ans); return 0; }