Advertisement
Guest User

Untitled

a guest
Mar 24th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define to_str(x) static_cast< std::ostringstream & >( \
  4. ( std::ostringstream() << std::dec << x ) ).str()
  5.  
  6. using namespace std;
  7. string s;
  8. ll dp[1000006][10];
  9. map<int, char> mp;
  10.  
  11. ll solve(int index, int found) {
  12. if (found == 8)
  13. return 1;
  14. if (index == (ll) s.size())
  15. return 0;
  16. if (dp[index][found] != -1)
  17. return dp[index][found];
  18. ll ans = 0;
  19. char ch = mp[found];
  20. for (int i = index; i < (int) s.size(); ++i) {
  21. if (s[i] != ch)
  22. continue;
  23. ans += solve(i + 1, found + 1);
  24. }
  25. return dp[index][found] = ans;
  26. }
  27.  
  28. int main() {
  29. // freopen("input.txt", "r", stdin);
  30. // freopen("output.txt", "w", stdout);
  31. ios_base::sync_with_stdio(0);
  32. cin.tie(0);
  33. mp[0] = 'E';
  34. mp[1] = 'N';
  35. mp[2] = 'G';
  36. mp[3] = 'I';
  37. mp[4] = 'N';
  38. mp[5] = 'E';
  39. mp[6] = 'E';
  40. mp[7] = 'R';
  41. memset(dp, -1, sizeof dp);
  42. cin >> s;
  43. ll ans = solve(0, 0);
  44. cout << ans << endl;
  45. return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement