Submission #1100879

#TimeUsernameProblemLanguageResultExecution timeMemory
1100879huantranSelotejp (COCI20_selotejp)C++17
0 / 110
302 ms524288 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() { #ifndef ONLINE_JUDGE freopen("TASK.inp", "r", stdin); freopen("TASK.out", "w", stdout); #endif // ONLINE_JUDGE ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<int> dp(1 << m, inf); 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) { if ((j == 0 || (bit(mask, j - 1) == 1) || adj[i][j - 1] == '.') && adj[i][j] == '#') dp[mask] = min(dp[mask], dp[mask ^ (1 << j)]) + 1; else dp[mask] = min(dp[mask], dp[mask ^ (1 << j)]); } else { if ((i == 0 || adj[i - 1][j] == '.') && adj[i][j] == '#') dp[mask] = min(dp[mask ^ (1 << j)], dp[mask]) + 1; else { dp[mask] = min(dp[mask], dp[mask ^ (1 << j)]); } } // cout << mask << ' ' << dp[mask] << '\n'; } // cout << "Check: " << j << ' ' << *min_element(dp.begin(), dp.end()) << ' ' << dp[0] << '\n'; } // cout << "Check: " << *min_element(dp.begin(), dp.end()) << '\n'; } int ans = inf; for (int i = 0; i < (1 << m); i++) ans = min(ans, dp[i]); cout << ans; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen("TASK.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("TASK.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...