fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7. const ll Mod = 1000000009LL;
  8. const ll Base = 271LL;
  9.  
  10. struct hashed_string{
  11.     private:
  12.     string s; ll n;
  13.     vector <ll> prefix;
  14.     vector <ll> pow;
  15.     public:
  16.     hashed_string(string a){
  17.         s = a; n = a.size();
  18.         prefix.assign(n, 0);
  19.         ll sum = 0;
  20.         pow.assign(n+1, 0);
  21.         pow[0] = 1;
  22.         for (int i = 1; i <= n; i++){
  23.             pow[i] = (pow[i-1] * Base) % Mod;
  24.         }
  25.         for (int i = 0; i < n; i++){
  26.             prefix[i] = ((sum * Base) % Mod + s[i] - 'a' + 1) % Mod;
  27.             sum = prefix[i];
  28.         }
  29.     }
  30.     hashed_string(){
  31.     }
  32.     ll get_hash(ll l, ll r){
  33.         ll x = prefix[r];
  34.         if (l >= 1){
  35.             l--;
  36.             x = ((x - prefix[l] * pow[r - l] % Mod) % Mod + Mod) % Mod;
  37.         }
  38.         return x;
  39.     }
  40. };
  41. void solve() {
  42.     ll n;
  43.     cin >> n;
  44.     vector <string> l1(n);
  45.     for (int i = 0; i< n; i++) cin >> l1[i];
  46.     sort(l1.begin(), l1.end(), [&](auto &a, auto &b){
  47.         return a.size() < b.size();
  48.     });
  49.     vector <hashed_string> v(n);
  50.     for (int i = 0; i < n; i++) v[i] = hashed_string(l1[i]);
  51.     vector <bool> good(n, true);
  52.     for (int i = 0; i < n; i++){
  53.         for (int j = i + 1; j < n; j++){
  54.             for (int x = 0; x + l1[i].size() - 1 < l1[j].size(); x++){
  55.                 if (v[i].get_hash(0, l1[i].size() - 1) == v[j].get_hash(x, x + l1[i].size() - 1)){
  56.                     good[i] = false;
  57.                     break;
  58.                 }
  59.             }
  60.             if (!good[i]) break;
  61.         }
  62.     }
  63.     vector <string> left_over;
  64.     for (int i = 0; i < n; i++) if (good[i]) left_over.push_back(l1[i]);
  65.     for (int i = 0; i < left_over.size(); i++) v[i] = hashed_string(left_over[i]);
  66.     ll cost[left_over.size()][left_over.size()];
  67.     for (int i = 0; i < left_over.size(); i++){
  68.         for (int j = 0; j < left_over.size(); j++){
  69.             if (i == j){
  70.                 cost[i][j] = left_over[i].size();
  71.             }
  72.             else{
  73.                 cost[i][j] = left_over[j].size();
  74.                 for (int x = 1; x <= min(left_over[i].size(), left_over[j].size()); x++){
  75.                     if (v[i].get_hash(left_over[i].size() - x, left_over[i].size() - 1) == v[j].get_hash(0, x - 1)){
  76.                         cost[i][j] = min(cost[i][j], (ll)left_over[j].size() - x);
  77.                     }
  78.                 }
  79.             }
  80.         }
  81.     }
  82.     n = left_over.size();
  83.     ll lim = (1LL << n);
  84.     ll dp[lim][n];
  85.     for (int i = 1; i < lim; i++){
  86.         for (int j = 0; j < n; j++){
  87.             dp[i][j] = inf;
  88.             if (i & (1LL << j)){
  89.                 if (__builtin_popcount(i) == 1){
  90.                     dp[i][j] = left_over[j].size();
  91.                     break;
  92.                 }
  93.                 for (int x = 0; x < n; x++){
  94.                     if (x != j && (i & (1LL << x))){
  95.                         dp[i][j] = min(dp[i][j], dp[i ^ (1LL << j)][x] + cost[x][j]);
  96.                     }
  97.                 }
  98.             }
  99.         }
  100.     }
  101.     ll answ = inf;  
  102.     for (int i = 0; i < n; i++){
  103.         answ = min(answ, dp[lim - 1][i]);
  104.     }
  105.     cout << answ << "\n";
  106. }
  107.  
  108. int main() {
  109.     ios::sync_with_stdio(false);
  110.     cin.tie(nullptr);
  111.  
  112.     ll t = 1;
  113.     while (t--) {
  114.         solve();
  115.     }
  116.  
  117.     return 0;
  118. }
Runtime error #stdin #stdout #stderr 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/7qCNAV
language:
C++14 (clang 8.0)
created:
2 hours ago
visibility:
secret

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!