Submission #1100886

#TimeUsernameProblemLanguageResultExecution timeMemory
1100886huantranSelotejp (COCI20_selotejp)C++17
110 / 110
23 ms604 KiB
#include <iostream> #include <algorithm> #include <cstring> #include <string.h> #include <vector> #include <math.h> #include <map> #include <set> #include <queue> #include <iomanip> #include <numeric> #include <random> #include <chrono> #include <fstream> #include <stack> #include <cmath> #define bit(x, i) (((x) >> (i)) & 1LL) #define rand rd #define PI acos(-1) using namespace std; typedef long long int ll; const int maxn = 1e5 + 5; const ll mod = 998244353; const int inf = 1e9 + 7; const ll base = 1e5 + 7; using pll = pair<ll, ll>; const string NAME = "LOCO"; const int NTEST = 100; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); ll Rand(ll l, ll r) { return l + rd() % (r - l + 1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<int> dp(1 << m, inf), ans(1 << m); vector<vector<char>> adj(n, vector<char>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cin >> adj[i][j]; } dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { for (int mask = 0; mask < (1 << m); mask++) { if (bit(mask, j) == 0) { ans[mask] = min(dp[mask], dp[mask ^ (1 << j)]); if ((j == 0 || (bit(mask, j - 1) == 1) || adj[i][j - 1] == '.') && adj[i][j] == '#') ans[mask]++; } else { if(adj[i][j] == '.') ans[mask] = inf; else ans[mask] = min(dp[mask], dp[mask ^ (1 << j)] + 1); } // cout << mask << ' ' << dp[mask] << '\n'; } dp = ans; // cout << "Check: " << j << ' ' << *min_element(dp.begin(), dp.end()) << ' ' << dp[0] << dp[1] << dp[2] << dp[3] << '\n'; } // cout << "Check: " << *min_element(dp.begin(), dp.end()) << '\n'; } int res = inf; for (int i = 0; i < (1 << m); i++) res = min(res, dp[i]); cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...