fork(5) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. ll solve(string &s,ll i,ll j,ll k,vector<vector<vector<ll>>> &dp){
  7. if(k == 0) return 1;
  8. if(i > j) return 0;
  9.  
  10. if(dp[i][j][k] != -1){
  11. return dp[i][j][k];
  12. }
  13.  
  14. if(k == 1){
  15. return dp[i][j][k] = j - i + 1;
  16. }
  17.  
  18. ll ans = 0;
  19.  
  20. if(i < j && s[i] == s[j]){
  21. ans = solve(s,i+1,j-1,k-2,dp);
  22. }
  23.  
  24. ans += solve(s,i+1,j,k,dp) + solve(s,i,j-1,k,dp) - solve(s,i+1,j-1,k,dp);
  25.  
  26. return dp[i][j][k] = ans;
  27. }
  28.  
  29. int main(){
  30. string s;
  31. cin>>s;
  32.  
  33. ll k;
  34. cin>>k;
  35.  
  36. ll n = s.length();
  37.  
  38. vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(n,vector<ll>(k+1,-1)));
  39.  
  40. ll ans = solve(s,0,n-1,k,dp);
  41.  
  42. cout<<ans<<endl;
  43. return 0;
  44. }
  45.  
  46.  
  47.  
  48.  
Runtime error #stdin #stdout #stderr 0.01s 5512KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc