fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7.  
  8. #define ll long long
  9. #define all(x) x.begin(),x.end()
  10.  
  11. typedef tree<
  12.     int,
  13.     null_type,
  14.     greater<int>,
  15.     rb_tree_tag,
  16.     tree_order_statistics_node_update
  17. > ordered_set;
  18.  
  19. ll MOD = 1000000007;
  20.  
  21. ll oo = 1e15;
  22.  
  23. ll const N = 1e4;
  24. ll matching[N + 1][20];
  25. ll stringsL[20];
  26. ll maskSize[1ll << 20];
  27. ll n, ans = oo;
  28.  
  29. ll len(ll x) {
  30.     ll ret = 0;
  31.     while (x) {
  32.         ret += (x & 1);
  33.         x /= 2;
  34.     }
  35.     return ret;
  36. }
  37.  
  38. string s;
  39.  
  40. ll go(ll mask) {
  41.     //base case
  42.     if (mask == 0) return 0ll;
  43.     //transition
  44.     ll ch1 = -oo;
  45.     ll size = 0;
  46.     if (~maskSize[mask]) {
  47.         size = maskSize[mask];
  48.     } else {
  49.         for (ll i = 0; i < n; i++) {
  50.             if ((mask & (1ll << i))) {
  51.                 size += stringsL[i];
  52.             }
  53.         }
  54.         maskSize[mask] = size;
  55.     }
  56.     for (ll i = 0; i < n; i++) {
  57.         if (mask & (1ll << i)) {
  58.             ll idx = go(mask ^ (1ll << i));
  59.             ll ch = matching[idx][i] + idx;
  60.             ll size2 = size;
  61.             if (ch >= s.length()) {
  62.                 ans = min(ans, size2);
  63.             }
  64.             ch1 = max(ch1, ch);
  65.         }
  66.     }
  67.     return ch1;
  68. }
  69.  
  70. void solve(ll test_case) {
  71.     cin >> s;
  72.     cin >> n;
  73.     memset(maskSize, -1, sizeof maskSize);
  74.     //preprocessing
  75.     string ts[n];
  76.     for (ll i = 0; i < n; i++) {
  77.         cin >> ts[i];
  78.         stringsL[i] = ts[i].length();
  79.     }
  80.     for (ll i = 0; i < n; i++) {
  81.         for (ll j = 0; j < s.length(); j++) {
  82.             ll s_ptr = j;
  83.             ll size = 0;
  84.             for (ll k = 0; s_ptr < s.length() && k < ts[i].length(); k++) {
  85.                 if (s[s_ptr] == ts[i][k]) {
  86.                     size++;
  87.                     s_ptr++;
  88.                 }
  89.             }
  90.             matching[j][i] = size;
  91.         }
  92.     }
  93.     //dp part
  94.     //definition:
  95.     //go(mask) -> maximum matching using elements mask
  96.     go((1ll << n) - 1);
  97.     cout << ans << endl;
  98. }
  99.  
  100. signed main() {
  101.     ios_base::sync_with_stdio(false);
  102.     cin.tie(NULL);
  103.     cout.tie(NULL);
  104. #ifndef ONLINE_JUDGE
  105.     freopen("input.txt", "r",stdin);
  106.     freopen("output.txt", "w",stdout);
  107. #endif
  108.     bool calc = false;
  109.     // calc = true;
  110.     if (calc) {
  111.         cout << 2 * 2 * 4 << endl;
  112.         // cout << (1ll << (20)) << endl;
  113.         return 0;
  114.     }
  115.     ll t = 1;
  116.     // cin >> t;
  117.     for (ll i = 1; i <= t; i++) {
  118.         solve(i);
  119.     }
  120. }
  121.  
Success #stdin #stdout 0.01s 11692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000
https://ideone.com/oESYfM
language:
C++14 (gcc 8.3)
created:
2 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!