fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. string s;
  5. ll q,l,r,f[5005][5005],ck[5005][5005],n;
  6. int main()
  7. {
  8.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9.     freopen("CNTPAL.INP", "r", stdin);
  10.     freopen("CNTPAL.OUT", "w", stdout);
  11.     cin >> s;
  12.     n = s.size();
  13.     s = ' ' + s;
  14.     memset(f, 0, sizeof f);
  15.     for(int i = n; i >= 1; i--)
  16.     {
  17.         for(int j = i; j <= n; j++)
  18.         {
  19.             if(i == j) ck[i][j] = 1;
  20.             else
  21.             {
  22.                 if(i == j - 1)
  23.                 {
  24.                     if(s[i] == s[j]) ck[i][j] = 1;
  25.                 }
  26.                 else
  27.                 {
  28.                     if(s[i] == s[j] && ck[i+1][j-1])
  29.                         ck[i][j] = 1;
  30.                 }
  31.             }
  32.         }
  33.     }
  34.     for(int i = n; i >= 1; i--)
  35.     {
  36.         for(int j = i; j <= n; j++)
  37.         {
  38.             if(i == j) f[i][j] = 1;
  39.             else
  40.             {
  41.                 if(i == j - 1)
  42.                 {
  43.                     if(s[i] == s[j]) f[i][j] = 3;
  44.                     else f[i][j] = 2;
  45.                 }
  46.                 else
  47.                 {
  48.                     f[i][j] = f[i+1][j] + f[i][j-1] - f[i+1][j-1];
  49.                     if(s[i] == s[j] && ck[i+1][j-1])
  50.                         f[i][j] += 1;
  51. //                    else
  52. //                    {
  53. //                        f[i][j] = f[i+1][j-1];
  54. //                    }
  55.                 }
  56.             }
  57.         }
  58.     }
  59.     cin >> q;
  60.     while(q--)
  61.     {
  62.         cin >> l >> r;
  63.         cout << f[l][r] << '\n';
  64.     }
  65. }
Success #stdin #stdout 0.03s 200480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tsPb8Q
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!