Submission #1210564

#TimeUsernameProblemLanguageResultExecution timeMemory
1210564btninhSelotejp (COCI20_selotejp)C++20
0 / 110
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define FOR(i, a, b) for(int i = a; i <= b; ++i) const int N = 1005; const int inf = 1e18; int n, m, dp[2][1 << 11][2]; char a[N][15]; int getBit(int msk, int i){ return (msk >> i) & 1; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j]; memset(dp, 0x3f, sizeof dp); dp[0][0][0] = 0; int cur = 1, lst = 0; FOR(i, 1, n){ FOR(j, 1, m){ FOR(msk, 0, (1 << m) - 1){ FOR(left, 0, 1){ int& val = dp[lst][msk][left]; if (val >= inf) continue; int bit = j - 1; if (a[i][j] == '.') { // không cần dán, reset bit dọc dp[cur][msk & ~(1 << bit)][0] = min(dp[cur][msk & ~(1 << bit)][0], val); } else { bool covered = left || getBit(msk, bit); // Nếu đã được bao phủ từ trái hoặc trên if (covered) { // Tiếp tục dán từ trái dp[cur][msk & ~(1 << bit)][1] = min(dp[cur][msk & ~(1 << bit)][1], val); // Tiếp tục dán từ trên dp[cur][msk | (1 << bit)][0] = min(dp[cur][msk | (1 << bit)][0], val); } else { // Dán mới ngang dp[cur][msk & ~(1 << bit)][1] = min(dp[cur][msk & ~(1 << bit)][1], val + 1); // Dán mới dọc dp[cur][msk | (1 << bit)][0] = min(dp[cur][msk | (1 << bit)][0], val + 1); } } } } // Reset trạng thái cũ FOR(msk, 0, (1 << m) - 1) FOR(l, 0, 1) dp[lst][msk][l] = inf; swap(cur, lst); } } int ans = inf; FOR(msk, 0, (1 << m) - 1) FOR(l, 0, 1) ans = min(ans, dp[lst][msk][l]); cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...