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.  
  8. const int M = 239;
  9. const int A = 30;
  10. const ll inf = ll(2e18) + 10;
  11.  
  12. struct Node {
  13.   Node* next[A];
  14.   Node* p;
  15.   int by;
  16.   int cost;
  17.   Node* link;
  18.   Node* go[A];
  19.   int id;
  20.  
  21.   Node() {
  22.     fill(next, next + A, nullptr);
  23.     p = nullptr;
  24.     by = -1;
  25.     cost = 0;
  26.     link = nullptr;
  27.     fill(go, go + A, nullptr);
  28.     id = -1;
  29.   }
  30.  
  31. } pool[M];
  32.  
  33. int last = 0;
  34.  
  35. Node *getNode() {
  36.   pool[last].id = last;
  37.   return pool + last++;
  38. }
  39.  
  40. int n;
  41. ll l;
  42. int a[M], b[M];
  43. vector<int> g[M];
  44. Node *root;
  45.  
  46. Node* go(Node *cur, int x);
  47. Node* getLink(Node *cur);
  48.  
  49. Node* getLink(Node *cur) {
  50.   if (cur->link == nullptr) {
  51.     if (cur == root || cur->p == root)
  52.       cur->link = root;
  53.     else
  54.       cur->link = go(getLink(cur->p), cur->by);
  55.   }
  56.   return cur->link;
  57. }
  58.  
  59. Node* go(Node *cur, int x) {
  60.   if (cur->go[x] == nullptr) {
  61.     if (cur->next[x] != nullptr)
  62.       cur->go[x] = cur->next[x];
  63.     else
  64.       cur->go[x] = cur == root ? root : go(getLink(cur), x);
  65.   }
  66.   return cur->go[x];
  67. }
  68.  
  69.  
  70. void read() {
  71.   cin >> n >> l;
  72.   for (int i = 0; i < n; ++i)
  73.     cin >> a[i];
  74.  
  75.   root = getNode();
  76.  
  77.   for (int i = 0; i < n; ++i) {
  78.     string s;
  79.     cin >> s;
  80.  
  81.     Node *cur = root;
  82.  
  83.     for (char c : s) {
  84.       int x = c - 'a';
  85.       if (cur->next[x] == nullptr) {
  86.         cur->next[x] = getNode();
  87.  
  88.         Node *nxt = cur->next[x];
  89.         nxt->p = cur;
  90.         nxt->by = x;
  91.  
  92.       }
  93.       cur = cur->next[x];
  94.     }
  95.  
  96.     cur->cost += a[i];
  97.   }
  98. }
  99.  
  100. struct Matrix {
  101.   ll a[M][M];
  102.  
  103.   Matrix() {
  104.     for (int i = 0; i < M; ++i)
  105.       fill(a[i], a[i] + M, -inf);
  106.   }
  107.  
  108.   ll* operator[](int x) {
  109.     return a[x];
  110.   }
  111. } I;
  112.  
  113. Matrix operator*(Matrix &A, Matrix &B) {
  114.   Matrix C;
  115.   for (int i = 0; i < M; ++i)
  116.     for (int k = 0; k < M; ++k)
  117.       for (int j = 0; j < M; ++j) {
  118.         C[i][j] = max(A[i][k] + B[k][j], C[i][j]);
  119.       }
  120.   return C;
  121. }
  122.  
  123. Matrix bin(Matrix A, ll to) {
  124.   Matrix B = I;
  125.   while (to) {
  126.     if (to & 1)
  127.       B = B * A;
  128.     A = A * A;
  129.     to >>= 1;
  130.   }
  131.   return B;
  132. }
  133.  
  134. void kill() {
  135.   for (int i = 0; i < M; ++i)
  136.     I[i][i] = 0;
  137.  
  138.   for (int i = 0; i < last; ++i) {
  139.     Node *cur = pool + i;
  140.     while (cur != root) {
  141.       b[i] += cur->cost;
  142.       cur = getLink(cur);
  143.     }
  144.  
  145.     cur = pool + i;
  146.     for (int x = 0; x < A; ++x)
  147.       g[i].push_back(go(cur, x) - pool);
  148.   }
  149.  
  150.   Matrix A;
  151.  
  152.   for (int i = 0; i < last; ++i)
  153.     for (int to : g[i])
  154.       A[i][to] = max<ll>(A[i][to], b[to]);
  155.  
  156.   A = bin(A, l);
  157.  
  158.   ll ans = 0;
  159.   for (int i = 0; i < last; ++i)
  160.     ans = max(ans, A[0][i]);
  161.  
  162.   cout << ans << "\n";
  163. }
  164.  
  165. int main() {
  166.   cout.precision(20);
  167.   cout << fixed;
  168.   ios_base::sync_with_stdio(false);
  169.   read();
  170.   kill();
  171. }
Success #stdin #stdout 1.29s 5748KB
comments (?)
stdin
copy 
2 98510
99 100
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbby
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz
stdout
copy 
98510
https://ideone.com/w3Yu73
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!