Advertisement
pb_jiang

CF991D AC

Jul 10th, 2023
808
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. // Problem: D. Bishwock
  2. // Contest: Codeforces - Codeforces Round 491 (Div. 2)
  3. // URL: https://codeforces.com/contest/991/problem/D
  4. // Memory Limit: 256 MB
  5. // Time Limit: 1000 ms
  6. //
  7. // Powered by CP Editor (https://cpeditor.org)
  8.  
  9. #include <assert.h>
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12. #ifndef __DEBUG__
  13. #define dbg(...) 42
  14. #endif
  15. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  16.  
  17. using ll = long long;
  18. using pii = pair<int, int>;
  19. using pll = pair<ll, ll>;
  20. using vl = vector<ll>;
  21. using vi = vector<int>;
  22.  
  23. int main(int argc, char **argv)
  24. {
  25.     int n;
  26.     string s1, s2;
  27.     cin >> s1 >> s2;
  28.     n = s1.size();
  29.     // 00 0, 0X 1, X0 2, XX 3
  30.     using a4i = array<int, 4>;
  31.     vector<a4i> dp(n + 1);
  32.     dp[0] = {0, 0, 0, 1};
  33.     for (int i = 0; i < n; ++i) {
  34.         int state = (s1[i] == 'X' ? 2 : 0) + (s2[i] == 'X' ? 1 : 0);
  35.         dp[i + 1][state] = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3]});
  36.         switch (state) {
  37.             case 0:
  38.                 dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + 1);
  39.                 dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + 1);
  40.                 dp[i + 1][3] = max(dp[i + 1][3], max(dp[i][1], dp[i][2]) + 1);
  41.                 break;
  42.             case 1:
  43.                 dp[i + 1][0] = dp[i + 1][2] = 0;
  44.                 dp[i + 1][3] = max(dp[i + 1][3], dp[i][0] + 1);
  45.                 break;
  46.             case 2:
  47.                 dp[i + 1][0] = dp[i + 1][1] = 0;
  48.                 dp[i + 1][3] = max(dp[i + 1][3], dp[i][0] + 1);
  49.                 break;
  50.             case 3:
  51.                 dp[i + 1][0] = dp[i + 1][1] = dp[i + 1][2] = 0;
  52.                 break;
  53.         }
  54.     }
  55.     for (auto x : dp)
  56.         dbg(x);
  57.     cout << max({dp[n][0], dp[n][1], dp[n][2], dp[n][3]}) - 1 << endl;
  58.     return 0;
  59. };
  60.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement