fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7. typedef pair<int, int> pii;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<int> vi;
  10.  
  11. #define fi first
  12. #define se second
  13. #define pp push_back
  14. #define all(x) (x).begin(), (x).end()
  15. #define Ones(n) __builtin_popcount(n)
  16. #define endl '\n'
  17. #define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
  18. //#define int long long
  19. #define debug(x) cout << (#x) << " = " << x << endl
  20.  
  21. void Gamal() {
  22.     ios_base::sync_with_stdio(false);
  23.     cin.tie(nullptr);
  24. #ifdef Clion
  25.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  26. #endif
  27. }
  28.  
  29. int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
  30. int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
  31.  
  32. const double EPS = 1e-9;
  33. const ll OO = 0X3F3F3F3F3F3F3F3F;
  34. const int N = 1e5 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;
  35.  
  36. int sum(int x) {
  37.     int ret = 0;
  38.     while (x) {
  39.         ret += x % 10;
  40.         x /= 10;
  41.     }
  42.     return ret;
  43. }
  44.  
  45.  
  46. struct AhoCorasick {
  47.     int states = 0;
  48.     vector<int> pi;
  49.     vector<int> dep;
  50.     vector<vector<int>> trie, patterns;
  51.     vector<vector<int>> dp;
  52.     vector<bool> bad;
  53.     AhoCorasick(){}
  54.     AhoCorasick(int n, int m = 10) {
  55.         pi = vector<int>(n + 10, -1);
  56.         patterns = vector<vector<int>>(n + 10);
  57.         trie = vector<vector<int>>(n + 10, vector<int>(m, -1));
  58.     }
  59.  
  60.     AhoCorasick(vector<string> &p, int n, int m = 10) {
  61.         /*
  62.          * MAKE SURE THAT THE STRINGS IN P ARE UNIQUE
  63.          * N is the summation of sizes of p
  64.          * M is the number of used alphabet
  65.         */
  66.         dep = vector<int>(n + 10, 0);
  67.         pi = vector<int>(n + 10, -1);
  68.         bad = vector<bool>(n + 10, false);
  69.         patterns = vector<vector<int>>(n + 10);
  70.         trie = vector<vector<int>>(n + 10, vector<int>(m, -1));
  71.         dp = vector<vector<int>>(n + 10, vector<int>(m, -1));
  72.  
  73.         for (int i = 0; i < p.size(); i++)
  74.             insert(p[i]);
  75.         build();
  76.     }
  77.  
  78.     void insert(string &s) {
  79.         int cur = 0, d = 0;
  80.         for (auto &it: s) {
  81.             if (trie[cur][it - '0'] == -1)
  82.                 trie[cur][it - '0'] = ++states;
  83.             cur = trie[cur][it - '0'];
  84.             dep[cur] = ++d;
  85.         }
  86.         bad[cur] = true;
  87.     }
  88.  
  89.     int nextState(int trieNode, int nxt) {
  90.         int cur = trieNode;
  91.         while (trie[cur][nxt] == -1)
  92.             cur = pi[cur];
  93.         return trie[cur][nxt];
  94.     }
  95.  
  96.     void build() {
  97.         queue<int> q;
  98.         for (int i = 0; i < 10; i++) {
  99.             if (trie[0][i] != -1)
  100.                 pi[trie[0][i]] = 0, q.push(trie[0][i]);
  101.             else
  102.                 trie[0][i] = 0;
  103.         }
  104.  
  105.         while (q.size()) {
  106.             int cur = q.front();
  107.             q.pop();
  108.             for (int i = 0; i < 10; i++) {
  109.                 if (trie[cur][i] == -1)
  110.                     continue;
  111.                 int f = nextState(pi[cur], i);
  112.                 pi[trie[cur][i]] = f;
  113.                 patterns[trie[cur][i]].insert(patterns[trie[cur][i]].end(), patterns[f].begin(), patterns[f].end());
  114.                 q.push(trie[cur][i]);
  115.             }
  116.         }
  117.     }
  118.  
  119.     int getNext(int node, char c) {
  120.         if (node == -1)return 0;
  121.         int &ret = dp[node][c - '0'];
  122.         if (~ret)return ret;
  123.         if (~trie[node][c - '0'])return ret = trie[node][c - '0'];
  124.         else return ret = getNext(pi[node], c);
  125.     }
  126.  
  127.  
  128. };
  129.  
  130.  
  131. AhoCorasick T;
  132. string n;
  133. int k;
  134. int dp[N][420];
  135.  
  136. int slv(int i, int node) {
  137.     if (i == n.size())return 0;
  138.     int &ret = dp[i][node];
  139.     if (~ret)return ret;
  140.     ret = 1 + slv(i + 1, node);
  141.     if (T.dep[node] == k) {
  142.         node = max(T.pi[node], 0);
  143.     }
  144.     int nxt = T.getNext(node, n[i]);
  145.     if (!T.bad[nxt]) {
  146.         ret = min(ret, slv(i + 1, nxt));
  147.     }
  148.     return ret;
  149. }
  150.  
  151. void solve() {
  152.     int sz;
  153.     cin >> sz >> k;
  154.     cin >> n;
  155.     int ans = 0;
  156.     string ns;
  157.     for (int i = 0; i < n.size(); ++i) {
  158.         if (n[i] == '1')ans++;
  159.         else ns += n[i];
  160.     }
  161.     n.swap(ns);
  162.  
  163.     if (n.empty()) {
  164.         cout << ans << endl;
  165.         return;
  166.     }
  167.     mem(dp, -1);
  168.     ans += slv(0, 0);
  169.     cout << ans << endl;
  170. }
  171.  
  172.  
  173. signed main() {
  174.     Gamal();
  175.     vector<string> v;
  176.     for (int i = 1; i <= 999999; ++i) {
  177.         string x = to_string(i);
  178.         if (find(all(x), '1') != x.end())continue;
  179.         int s = sum(i);
  180.         if (i % (s * s * s) == 0) {
  181.             v.emplace_back(x);
  182.         }
  183.     }
  184.     sort(all(v), [&](string &a, string &b) {
  185.         return a.size() < b.size();
  186.     });
  187.     set<string> k;
  188.     auto check = [&](string &s) {
  189.         for (int i = 0; i < s.size(); ++i) {
  190.             for (int j = i; j < s.size(); ++j) {
  191.                 if (k.count(s.substr(i, j - i + 1)))return true;
  192.             }
  193.         }
  194.         return false;
  195.     };
  196.  
  197.     vector<string> tot;
  198.     for (auto &s: v) {
  199.         if (check(s))continue;
  200.         tot.emplace_back(s);
  201.         k.insert(s);
  202.     }
  203.     T = AhoCorasick(tot, 420);
  204.  
  205.     int t = 1;
  206. //    cin >> t;
  207.     while (t--) {
  208.         solve();
  209.     }
  210. }
Success #stdin #stdout 0.16s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/KBtaPW
language:
C++14 (gcc 8.3)
created:
6 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!