pb_jiang

ABC407D

May 25th, 2025
281
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <assert.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #ifndef __DEBUG__
  5. #define dbg(...) 42
  6. #endif
  7. template <class T>
  8. using mpq = priority_queue<T, vector<T>, greater<T>>;
  9.  
  10. namespace rngs = std::ranges;
  11. using ll = long long;
  12. using a2l = array<ll, 2>;
  13. using pll = pair<ll, ll>;
  14. using vl = vector<ll>;
  15.  
  16. int main(int argc, char **argv) {
  17.     std::ios::sync_with_stdio(false);
  18.     std::cin.tie(nullptr);
  19.  
  20.     ll h, w, xall = 0;
  21.     cin >> h >> w;
  22.     vector<vl> a(h, vl(w));
  23.     for (auto &row : a)
  24.         for (auto &col : row)
  25.             cin >> col, xall ^= col;
  26.  
  27.     vector<vl> mark(h, vl(w));
  28.     ll ans = 0;
  29.     ll cnt = 0;
  30.     auto dfs = [&](auto &&self, ll x, ll y, ll acc) -> void {
  31.         cnt += 1;
  32.         if (y >= w)
  33.             y = 0, x += 1;
  34.         if (x >= h) {
  35.             ans = max(ans, acc);
  36.             return;
  37.         }
  38.  
  39.         if (mark[x][y] == 0) {
  40.             self(self, x, y + 1, acc);
  41.             if (x + 1 < h && !mark[x + 1][y]) {
  42.                 mark[x][y] = mark[x + 1][y] = 1;
  43.                 self(self, x, y + 1, acc ^ a[x][y]);
  44.                 mark[x][y] = mark[x + 1][y] = 0;
  45.             }
  46.             if (y + 1 < w && !mark[x][y + 1]) {
  47.                 mark[x][y] = mark[x][y + 1] = 1;
  48.                 self(self, x, y + 1, acc ^ a[x][y]);
  49.                 mark[x][y] = mark[x][y + 1] = 0;
  50.             }
  51.         } else
  52.             self(self, x, y + 1, acc ^ a[x][y]);
  53.     };
  54.  
  55.     dfs(dfs, 0, 0, xall);
  56.     cout << ans << '\n';
  57.     dbg(cnt);
  58.  
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment