結果
問題 | No.43 野球の試合 |
ユーザー | evawenis |
提出日時 | 2020-07-09 18:10:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 917 bytes |
コンパイル時間 | 4,905 ms |
コンパイル使用メモリ | 210,088 KB |
最終ジャッジ日時 | 2025-01-11 17:10:56 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
ソースコード
#include<bits/stdc++.h> using namespace std; int main(){ cin.tie(0),ios::sync_with_stdio(false); int n; cin>>n; vector<string>s(n); for(auto&&i:s)cin>>i; vector<pair<int,int>>sc(n,{0,-1}); sc.at(0).second=0; for(int y=0;y<n;++y){ for(int x=0;x<n;++x){ if(s.at(y).at(x)=='#')break; if(s.at(y).at(x)!='x')++sc.at(y).first; else ++sc.at(x).first; } } int ans=n+1; for(int i=0;i<(1<<n);++i){ for(int j=0;j<(1<<n);++j){ vector<pair<int,int>>tsc=sc; for(int y=0;y<n;++y){ if(!(i&(1<<y)))continue; for(int x=0;x<n;++x){ if(!(j&(1<<x))||x<=y||s.at(y).at(x)!='-')continue; ++tsc.at(y).first; --tsc.at(x).first; } } stable_sort(tsc.rbegin(),tsc.rend()); int tans=n+1; for(int k=0,fix=1;k<n;++k){ if(k>0&&tsc.at(k)==tsc.at(k-1))--fix; if(tsc.at(k).second==0){ tans=k+fix; break; } } ans=min(ans,tans); } } cout<<ans<<"\n"s; }