arten_1337

Untitled

Feb 13th, 2020
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define IOS                  \
  5.     ios::sync_with_stdio(0); \
  6.     cin.tie(0);              \
  7.     cout.tie(0);
  8. #define endl "\n"
  9. #define int long long
  10. #define watch(x) cout << (#x) << " is " << (x) << endl;
  11.  
  12. int dp[1001][1001];
  13. int palindrome(string s, int l, int r)
  14. {
  15.     if (l == r)
  16.     {
  17.         return dp[l][r] = 2;
  18.     }
  19.     if (r - l == 1)
  20.     {
  21.         if (s[l] == s[r])
  22.             return dp[l][r] = 2;
  23.         else
  24.         {
  25.             return dp[l][r] = 1;
  26.         }
  27.     }
  28.     if (dp[l][r])
  29.         return dp[l][r];
  30.     if ((s[l] == s[r]) && palindrome(s, l + 1, r - 1))
  31.         dp[l][r] = 2;
  32.     else
  33.         dp[l][r] = 1;
  34.     return dp[l][r];
  35. }
  36. int32_t main()
  37. {
  38.     IOS;
  39.  
  40.     int n, m, ans;
  41.     string s;
  42.     cin >> n >> s >> m;
  43.     for (int i = 0; i < m; i++)
  44.     {
  45.         int left, right;
  46.         cin >> left >> right;
  47.         left--, right--;
  48.         if (!dp[left][right])
  49.         {
  50.             ans = palindrome(s, left, right);
  51.         }
  52.         else
  53.         {
  54.             ans = dp[left][right];
  55.         }
  56.         cout << ((ans == 1) ? "NO" : "YES") << endl;
  57.     }
  58.  
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment