TLE on test #5

不说别的，这时间复杂度是 $O(n^2)$吧？那为什么会超呢

#include<bits/stdc++.h>
using namespace std;
string a;
int dp[5005][5005];
int q,l,r;
bool hw[5005][5005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0)
	//freopen("data.in","r",stdin);
	cin>>a;
    cin>>q;
    int n=a.length();
	for(int i=0;i<n;i++){
		int dis=0;
		while(i-dis>=0&&i+dis<n){
			hw[i-dis][i+dis]=1;
			dis++;
			if(a[i-dis]!=a[i+dis])break;
		}
	}
    for(int i=0;i<n;i++){
        int dis=1;
        while(i-dis+1>=0&&i+dis<n){
            if(a[i-dis+1]!=a[i+dis])break;
            hw[i-dis+1][i+dis]=1;
            dis++;
        }
    }
	for(int i=1;i<=n;i++)dp[i][i]=1;
	for(int i=1;i<n;i++)dp[i][i+1]=((a[i-1]==a[i])+2);
	for(int L=3;L<=n;L++){
		for(int i=1;i+L-1<=n;i++){
			int j=i+L-1;
			dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]+hw[i-1][j-1];
		}
	}
	for(int i=1;i<=q;i++){
		cin>>l>>r;
		cout<<dp[l][r]<<endl; 
	}
	return 0;
}