Submission #855908

#TimeUsernameProblemLanguageResultExecution timeMemory
855908wakandaaaSelotejp (COCI20_selotejp)C++17
110 / 110
23 ms1624 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define getbit(x, i) (((x) >> (i)) & 1) #define bit(x) (1 << (x)) #define popcount __builtin_popcountll mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); long long rand(long long l, long long r) { return l + rd() % (r - l + 1); } const int N = 1e3 + 5; const int mod = 1e9 + 7; // 998244353; const int lg = 25; // lg + 1 const int inf = 1e9; // INT_MAX; const long long llinf = 1e18; // LLONG_MAX; template<class X, class Y> bool minimize(X &a, Y b) { return a > b ? (a = b, true) : false; } template<class X, class Y> bool maximize(X &a, Y b) { return a < b ? (a = b, true) : false; } template<class X, class Y> bool add(X &a, Y b) { a += b; while (a >= mod) a -= mod; while (a < 0) a += mod; return true; } int n, m; char c[N][N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> c[i][j]; vector<int> pf(1 << m, inf), f(1 << m); pf[0] = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { for (int mask = 0; mask < bit(m); ++mask) { if (getbit(mask, j)) { if (c[i][j] == '.') f[mask] = inf; else f[mask] = min(pf[mask], pf[mask ^ bit(j)] + 1); } else { f[mask] = min(pf[mask], pf[mask ^ bit(j)]); if (c[i][j] == '#' && (j == 0 || getbit(mask, j - 1) || c[i][j - 1] == '.')) f[mask]++; } } pf = f; } cout << *min_element(all(pf)); return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...