245H - Queries for Number of Palindromes - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) (x).begin(), (x).end()
const int MAXN = 5005;

int dp[MAXN][MAXN];
int is[MAXN][MAXN];

void fill()
{
	for(int i = 0; i <= 5001; i++)
	{
		for(int j = 0; j <= 5001; j++)
			is[i][j] = 1;
	}
}

int32_t main()
{
	fill();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    string str; cin >> str;
    int boyut = str.size();
    for(int i = boyut; i >= 1; i--)
    {
        for(int j = i; j <= boyut; j++)
        {
            if(i == j) continue;

            if(str[i -1] == str[j -1]) is[i][j] = is[i +1][j -1];
            else is[i][j] = 0;
        }
    }

    for(int i = boyut; i >= 1; i--)
    {
        for(int j = i; j <= boyut; j++)
        {
            if(i == j)
            {
                dp[i][j] = 1;
                continue;
            }

            dp[i][j] = is[i][j];
            dp[i][j] += dp[i +1][j] + dp[i][j -1] - dp[i +1][j -1];
        }
    }

    int test; cin >> test;
    while(test--)
    {
        int l, r; cin >> l >> r;
        cout << dp[l][r] << "\n";
    }
 
    return 0;
}