Why am I getting TLE n=5000 so n^2 shall pass.......

Revision en1, by Master_Sahil, 2023-06-08 09:43:18

include<bits/stdc++.h>

using namespace std;

define nl <<endl;

typedef pair<ll,ll> pl; typedef vector vl; typedef vector vb; typedef vector vd; typedef vector vs;

define opt(v) for(auto x: v) cout << x << ' '; cout nl

const ll mod = 1000000007; const ll N = 2e5+10;

define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);

void solve(){

string s;
cin>>s;
ll q;
cin>>q;
ll n=s.size();
bool dp[n+3][n+3];

fo(i,n+3){ fo(j,n+3){ dp[i][j]=false; } } for(int l=n-1;l>=0;--l){ fo(r,n){ if(l>r) continue; ll len=r-l+1; if(len==1) dp[l][r]=true; else if(len==2 && s[l]==s[r]) dp[l][r]=true; else if(s[l]==s[r] && dp[l+1][r-1]){ dp[l][r]=true; } else{ dp[l][r]=false; } } } ll cnt[n+1][n+1]; fo(i,n+1){ fo(j,n+1){ cnt[i][j]=0; } } fo(i,n){ ll sm=0; for(int j=i;j<n;++j){ if(dp[i][j]){ sm++; } cnt[i][j]=sm; } } fo(j,n){ fop(i,1,n-1){ cnt[i][j]=cnt[i-1][j]+cnt[i][j]; } } while(q--){ ll a,b; cin>>a>>b; ll ans=0; a--; b--;

// fop(i,a,b){
//     ans+=cnt[i][b];
// }
if(a==0)
ans=cnt[b][b];
else{
ans= cnt[b][b]-cnt[a-1][b];
}
cout<<ans<<endl;
// fop(j,a,b){****
Spoiler

**** // ans+=cnt[] // } } } signed main(){ IOS ll t=1; while(t--) solve(); return 0; }

History

Revisions

Rev. Lang. By When Δ Comment
en2 Master_Sahil 2023-06-08 09:47:27 72
en1 Master_Sahil 2023-06-08 09:43:18 2423 Initial revision (published)