結果
問題 | No.3060 Erase Binary Matrix |
ユーザー |
![]() |
提出日時 | 2024-10-20 20:30:15 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 803 bytes |
コンパイル時間 | 10,854 ms |
コンパイル使用メモリ | 221,084 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-12 00:39:21 |
合計ジャッジ時間 | 9,693 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 49 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/dsu> using namespace std; int main(){ int H, W; cin >> H >> W; assert(1 <= H <= 500); assert(1 <= W <= 500); vector<string> A(H + 2); for(int i = 1; i <= H; i++){ cin >> A[i]; assert(A[i].size() == W); for(auto c : A[i]){ assert(c == '0' || c == '1'); } } A[0] = string(W, '0'); A[H + 1] = string(W, '1'); sort(A.begin(), A.end()); vector<int>dp(H + 2, 1e9); dp[0] = 0; for(int i = 0; i < H + 2; i++){ for(int j = i + 1; j < H + 2; j++){ bool ok = true; for(int k = 0; k < W; k++){ if(A[i][k] == '1' && A[j][k] == '0'){ ok = false; break; } } if(ok){ dp[j] = min(dp[j], dp[i] + (j - i - 1)); } } } cout << dp[H + 1] << endl; }