fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. //#pragma GCC optimize("Ofast")
  4. //#pragma GCC target("avx,avx2,fma")
  5. //#pragma GCC optimization ("unroll-loops")
  6.  
  7. #define ll long long
  8.  
  9. #define sl(n) scanf("%lld", &n)
  10. #define ss(n) scanf("%s", n)
  11. #define sch(n) scanf("%c", &n)
  12. #define sf(n) scanf("%lf", &n)
  13.  
  14. #define PI 2*acos(0.0)
  15. #define INF (1LL<<62)
  16.  
  17. #define pll pair<ll,ll>
  18.  
  19. #define pb push_back
  20. #define eb emplace_back
  21. #define fr first
  22. #define sc second
  23. #define srt(v) sort(v.begin(), v.end())
  24. using namespace std;
  25.  
  26. char s[20];
  27. ll len;
  28.  
  29. ll dp[17][17];
  30. ll solve(ll rowLeft, ll pos) {
  31.     if (pos == len - 1) {
  32.         return 1;
  33.     }
  34.  
  35.     ll &ret = dp[rowLeft][pos];
  36.  
  37.     if (ret != -1) return ret;
  38.  
  39.     ret = 0;
  40.     ret += solve(rowLeft, pos + 1);
  41.     if (rowLeft > 1) {
  42.         ret += solve(rowLeft - 1, pos + 1);
  43.     }
  44.  
  45. //    cout << rowLeft << " " << pos << " " << ret << endl;
  46.  
  47.     return ret;
  48. }
  49.  
  50. int main() {
  51.     ll n;
  52.     sl(n);
  53.     ss(s);
  54.     len = strlen(s);
  55.  
  56.     ll ans = 0;
  57.  
  58.     if (n - len > 0) {
  59.         ans += (1LL << (len-1));
  60.         ans *= n - len;
  61.     }
  62.  
  63. //    cout << ans << endl;
  64.  
  65.     memset(dp, -1, sizeof(dp));
  66.  
  67.     ll rowLeft = min(n, len);
  68.     while (rowLeft) {
  69.         ans += solve(rowLeft--, 0);
  70.     }
  71.  
  72.     printf("%lld\n", ans);
  73.  
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 4772KB
comments (?)
stdin 
15
codeforces
stdout 
5376
https://ideone.com/v5QDBo
language:
C++14 (gcc 8.3)
created:
3 years 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!