結果
問題 |
No.1560 majority x majority
|
ユーザー |
![]() |
提出日時 | 2024-08-07 21:10:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 499 ms / 2,000 ms |
コード長 | 898 bytes |
コンパイル時間 | 1,367 ms |
コンパイル使用メモリ | 100,704 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-08-07 21:10:11 |
合計ジャッジ時間 | 6,151 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 26 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m; cin>>n>>m; vector<vector<int>> s(n,vector<int>(m)); for(int i = 0;i<n;i++) for(int j = 0;j<m;j++) cin>>s[i][j]; vector<ll> dp(1<<m,0); dp[0] = 1; for(int i = 0;i<1<<m;i++){ vector<int> use(n,0); for(int j = 0;j<n;j++){ bool fn = false; for(int k = 0;k<m;k++) if(i>>k&1&&s[j][k]==0) fn = true; if(!fn) use[j] = 1; } for(int j = 0;j<m;j++) if(~i>>j&1){ int cnt = 0; int ok = 0; for(int k = 0;k<n;k++) if(use[k]) { cnt++; if(s[k][j]==1) ok++; } if(2*ok>=cnt) dp[i|(1<<j)] += dp[i]; } } cout<<dp[(1<<m)-1]<<endl; }