fork download 
  1. #pragma GCC optimize("O3")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. #define pb push_back
  7. #define fi first
  8. #define se second
  9. #define all(v) v.begin(), v.end()
  10.  
  11. using namespace std;
  12. using ll = int64_t;
  13.  
  14. struct Node {
  15.   map<char, Node*> next;
  16.   Node* suffix_link;
  17.   Node* parent;
  18.   vector<int> ends;
  19.   char c;
  20.   int len;
  21.   int id;
  22.  
  23.   Node() : suffix_link(0), parent(0), c(0), len(0), id(0) {}
  24.   Node(Node* p, char x, int y) : suffix_link(0), parent(p), c(x), len(y), id(0) {}
  25. };
  26.  
  27. Node root;
  28.  
  29. void add(Node* cursor, string s, int i) {
  30.   for (char c : s) {
  31.     if (!cursor->next.count(c)) {
  32.       cursor->next[c] = new Node(cursor, c, cursor->len + 1);
  33.     }
  34.     cursor = cursor->next[c];
  35.   }
  36.   cursor->ends.pb(i);
  37. }
  38.  
  39. Node* get_sl(Node* n, char c) {
  40.   Node* ans = n;
  41.   while (ans != &root && !ans->next.count(c)) {
  42.     ans = ans->suffix_link;
  43.   }
  44.   if (ans->next.count(c)) {
  45.     ans = ans->next[c];
  46.   }
  47.   return ans;
  48. }
  49.  
  50. vector<Node*> build() {
  51.   queue<Node*> q;
  52.   vector<Node*> v;
  53.   q.push(&root);
  54.   int ids = 0;
  55.   while (!q.empty()) {
  56.     Node* n = q.front(); q.pop();
  57.     v.pb(n);
  58.     n->id = ids++;
  59.     if (n == &root || n->parent == &root) {
  60.       n->suffix_link = &root;
  61.     } else {
  62.       Node* ans = n->parent->suffix_link;
  63.       while (ans != &root && !ans->next.count(n->c)) {
  64.         ans = ans->suffix_link;
  65.       }
  66.       if (ans->next.count(n->c)) {
  67.         ans = ans->next[n->c];
  68.       }
  69.       n->suffix_link = get_sl(n->parent->suffix_link, n->c);
  70.  
  71.     }
  72.     for (auto p : n->next) {
  73.       q.push(p.second);
  74.     }
  75.   }
  76.   return v;
  77. }
  78.  
  79. const int N = 202, D = 27;
  80.  
  81. int g[N + 2][D];
  82. ll d[N + 2][N][N];
  83. bool can[N + 2][N][N];
  84. ll weight[N + 2];
  85.  
  86. int main() {
  87.   ios_base::sync_with_stdio(false);
  88.   cin.tie(nullptr);
  89.  
  90.   int n;
  91.   cin >> n;
  92.   ll length;
  93.   cin >> length;
  94.  
  95.   vector<ll> adds(n);
  96.   for (int i = 0; i < n; i++)
  97.     cin >> adds[i];
  98.  
  99.   for (int i = 0; i < n; i++) {
  100.     string s;
  101.     cin >> s;
  102.     add(&root, s, i);
  103.   }
  104.  
  105.   auto all_nodes = build();
  106.   int k = all_nodes.size();
  107.  
  108.   for (Node* node : all_nodes) {
  109.     auto cursor = node;
  110.     while (cursor != &root) {
  111.       for (int i : cursor->ends) {
  112.         weight[node->id] += adds[i];
  113.       }
  114.       cursor = cursor->suffix_link;
  115.     }
  116.     //cerr << weight[node->id] << endl;
  117.     for (char c = 'a'; c <= ('z' + 1); c++) {
  118.       Node* jump = get_sl(node, c);
  119.       g[node->id][c - 'a'] = jump->id;
  120.     }
  121.   }
  122.  
  123.   for (int i = 0; i < k; i++) {
  124.     can[0][i][i] = true;
  125.   }
  126.  
  127.   for (int m = 0; m < N - 1; m++) {
  128.     for (int s = 0; s < k; s++) {
  129.       for (int e = 0; e < k; e++) {
  130.         if (can[m][s][e]) {
  131.           for (int l = 0; l < D; l++) {
  132.             int v = g[e][l];
  133.             can[m + 1][s][v] = true;
  134.             d[m + 1][s][v] = max(d[m + 1][s][v], d[m][s][e] + weight[v]);
  135.           }
  136.         }
  137.       }
  138.     }
  139.   }
  140.  
  141.   ll res = 0;
  142.  
  143.   for (int i = 0; i <= min(ll(N), length + 1); i++)
  144.     res = max(res, d[i][0][0]);
  145.  
  146.  
  147.   for (int prefix = 0; prefix <= N; prefix++) {
  148.     for (int suffix = 0; suffix <= N; suffix++) {
  149.       ll remain = length - suffix - prefix;
  150.       if (remain > 1) {
  151.         for (int cycle = 1; cycle <= N; cycle++) {
  152.           if (remain % cycle == 0) {
  153.             ll times = remain / cycle;
  154.             for (int s = 0; s < k; s++) {
  155.               if (can[prefix][0][s] && can[suffix + 1][s][0] && can[cycle][s][s]) {
  156.                 res = max(res, d[prefix][0][s] + d[suffix + 1][s][0] + d[cycle][s][s] * times);
  157.               }
  158.             }
  159.           }
  160.         }
  161.       }
  162.     }
  163.   }
  164.  
  165.  
  166.   cout << res << endl;
  167.  
  168.  
  169.  
  170.  
  171.   return 0;
  172. }
  173.  
Success #stdin #stdout 2.75s 76736KB
comments (?)
stdin 
2 98510
99 100
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbby
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz
stdout 
98509
https://ideone.com/h33YPN
language:
C++14 (gcc 8.3)
created:
8 years 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!