fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. const int maxn = 522, sigma = 26;
  8. int a[maxn];
  9.  
  10. int to[maxn][sigma];
  11. int link[maxn], cost[maxn];
  12. int sz = 1;
  13. void add_str(string s, int n)
  14. {
  15.     int v = 0;
  16.     for(auto c: s)
  17.     {
  18.         c -= 'a';
  19.         if(!to[v][c])
  20.             to[v][c] = sz++;
  21.         v = to[v][c];
  22.     }
  23.     cost[v] += a[n];
  24. }
  25.  
  26. void push_links()
  27. {
  28.     int que[sz];
  29.     int st = 0, fi = 1;
  30.     que[0] = 0;
  31.     while(st < fi)
  32.     {
  33.         int v = que[st++];
  34.         int u = link[v];
  35.         cost[v] += cost[u];
  36.         for(int c = 0; c < sigma; c++)
  37.         {
  38.             if(to[v][c])
  39.             {
  40.                 link[to[v][c]] = v ? to[u][c] : 0;
  41.                 que[fi++] = to[v][c];
  42.             }
  43.             else
  44.             {
  45.                 to[v][c] = to[u][c];
  46.             }
  47.         }
  48.     }
  49. }
  50.  
  51. signed main()
  52. {
  53.     //freopen("input.txt", "r", stdin);
  54.     ios::sync_with_stdio(0);
  55.     cin.tie(0);
  56.     int n, l;
  57.     cin >> n >> l;
  58.     for(int i = 0; i < n; i++)
  59.         cin >> a[i];
  60.     for(int i = 0; i < n; i++)
  61.     {
  62.         string s;
  63.         cin >> s;
  64.         add_str(s, i);
  65.     }
  66.     push_links();
  67.     const int logn = 50;
  68.     int best[logn][sz][sz];
  69.     memset(best, -1, sizeof(best));
  70.     for(int i = 0; i < sz; i++)
  71.         for(int c = 0; c < sigma; c++)
  72.             best[0][i][to[i][c]] = cost[to[i][c]];
  73.     for(int z = 1; z < logn; z++)
  74.         for(int k = 0; k < sz; k++)
  75.             for(int i = 0; i < sz; i++)
  76.                 for(int j = 0; j < sz; j++)
  77.                     if(best[z - 1][i][k] != -1 && best[z - 1][k][j] != -1)
  78.                         best[z][i][j] = max(best[z][i][j], best[z - 1][i][k] + best[z - 1][k][j]);
  79.     int ans[sz][sz];
  80.     memset(ans, -1, sizeof(ans));
  81.     for(int i = 0; i < sz; i++)
  82.         ans[i][i] = 0;
  83.     for(int z = 0; z < logn; z++)
  84.     {
  85.         if((l >> z) & 1)
  86.         {
  87.             int tmp[sz][sz];
  88.             memset(tmp, -1, sizeof(tmp));
  89.             for(int k = 0; k < sz; k++)
  90.                 for(int i = 0; i < sz; i++)
  91.                     for(int j = 0; j < sz; j++)
  92.                         if(ans[i][k] != -1 && best[z][k][j] != -1)
  93.                             tmp[i][j] = max(tmp[i][j], ans[i][k] + best[z][k][j]);
  94.             memcpy(ans, tmp, sizeof(ans));
  95.         }
  96.     }
  97.     int out = 0;
  98.     for(int i = 0; i < sz; i++)
  99.         out = max(out, ans[0][i]);
  100.     cout << out << "\n";
  101. 	return 0;
  102. }
Runtime error #stdin #stdout 0s 3528KB
comments (?)
stdin
copy 
2 98510
99 100
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbby
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz
stdout
copy 
Standard output is empty
https://ideone.com/mJcex4
language:
C++14 (gcc 8.3)
created:
7 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!