Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define IOS \
- ios::sync_with_stdio(0); \
- cin.tie(0); \
- cout.tie(0);
- #define endl "\n"
- #define int long long
- #define watch(x) cout << (#x) << " is " << (x) << endl;
- int dp[1001][1001];
- int palindrome(string s, int l, int r)
- {
- if (l == r)
- {
- return dp[l][r] = 2;
- }
- if (r - l == 1)
- {
- if (s[l] == s[r])
- return dp[l][r] = 2;
- else
- {
- return dp[l][r] = 1;
- }
- }
- if (dp[l][r])
- return dp[l][r];
- if ((s[l] == s[r]) && palindrome(s, l + 1, r - 1))
- dp[l][r] = 2;
- else
- dp[l][r] = 1;
- return dp[l][r];
- }
- int32_t main()
- {
- IOS;
- int n, m, ans;
- string s;
- cin >> n >> s >> m;
- for (int i = 0; i < m; i++)
- {
- int left, right;
- cin >> left >> right;
- left--, right--;
- if (!dp[left][right])
- {
- ans = palindrome(s, left, right);
- }
- else
- {
- ans = dp[left][right];
- }
- cout << ((ans == 1) ? "NO" : "YES") << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment