Submission #475594

#TimeUsernameProblemLanguageResultExecution timeMemory
475594abc864197532Selotejp (COCI20_selotejp)C++17
110 / 110
147 ms364 KiB
/* * ## ##### #### #### # # #### * # # # # # # # # # # # # * # # ##### # # # # # # # * ###### # # # # # # ## # # # * # # # # # # # # ## ## # # * # # ##### #### #### # # #### */ #include <bits/stdc++.h> using namespace std; #define lli long long int #define mp make_pair #define pb push_back #define eb emplace_back #define pii pair <int, int> #define X first #define Y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define info() cout << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { for (; l != r; ++l) cout << *l << " \n"[l + 1 == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.X >> a.Y; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.X << ", " << a.Y << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; if (a.empty()) return o << "{}"; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } template <typename T> struct vv : vector <vector <T>> { vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {} vv() {} }; template <typename T> struct vvv : vector <vv <T>> { vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {} vvv() {} }; #ifdef Doludu #define test(args...) info(), abc("[" + string(#args) + "]", args) #define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout); #else #define test(args...) void(0) #define owo ios::sync_with_stdio(false); cin.tie(0) #endif const int mod = 998244353, N = 300001, logN = 20, K = 111; int main () { owo; int n, m; cin >> n >> m; vector <string> t(n); for (int i = 0; i < n; ++i) cin >> t[i]; vector <int> pre(1 << m + 1, 1 << 30), dp; pre[0] = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { dp.assign(1 << m + 1, 1 << 30); for (int s = 0; s < 1 << m + 1; ++s) { if (t[i][j] == '#') { if (s >> m & 1 && s >> j & 1) { dp[s ^ (1 << m)] = min(dp[s ^ (1 << m)], pre[s]); dp[s ^ (1 << j)] = min(dp[s ^ (1 << j)], pre[s]); } else if (s >> m & 1 || s >> j & 1) dp[s] = min(dp[s], pre[s]); else { dp[s ^ (1 << m)] = min(dp[s ^ (1 << m)], pre[s] + 1); dp[s ^ (1 << j)] = min(dp[s ^ (1 << j)], pre[s] + 1); } } else { int nxt = s; if (s >> m & 1) nxt ^= 1 << m; if (s >> j & 1) nxt ^= 1 << j; dp[nxt] = min(dp[nxt], pre[s]); } } pre = dp; } for (int s = 0; s < 1 << m; ++s) pre[s] = min(pre[s], pre[s ^ (1 << m)]), pre[s ^ (1 << m)] = 1 << 30; } int ans = 1 << 30; for (int i : pre) ans = min(ans, i); cout << ans << endl; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:64:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   64 |     vector <int> pre(1 << m + 1, 1 << 30), dp;
      |                           ~~^~~
Main.cpp:68:30: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   68 |             dp.assign(1 << m + 1, 1 << 30);
      |                            ~~^~~
Main.cpp:69:40: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   69 |             for (int s = 0; s < 1 << m + 1; ++s) {
      |                                      ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...