結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 3 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 3 ms
5,248 KB |
testcase_08 | AC | 3 ms
5,248 KB |
testcase_09 | AC | 4 ms
5,248 KB |
testcase_10 | AC | 3 ms
5,248 KB |
ソースコード
#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; }