fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define cint const int
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8. #define vi vector<int>
  9. #define vii vector<vi>
  10. #define pb push_back
  11. #define pq priority_queue
  12. #define mid(l, r) ((l + r) >> 1)
  13. #define left(id) (id << 1)
  14. #define right(id) (id << 1 | 1)
  15. #define cntbit(mask) __builtin_popcountll(mask)
  16. #define BIT(mask, i) (mask & (1ll << (i)))
  17. #define ONBIT(mask, i) (mask | (1ll << (i)))
  18.  
  19. const int MAXN = 1e5 + 15;
  20. const int oo   = 1e18;
  21. const int MOD  = 1e9 + 7;
  22.  
  23. int n, m, q;
  24. vector<string> P;
  25. vector<int> order;
  26. vector<string> S;
  27.  
  28. void PROCESS() {
  29.     freopen("ojfactory.inp", "r", stdin);
  30.     freopen("ojfactory.out", "w", stdout);
  31.     cin >> n >> m >> q;
  32.  
  33.     P.resize(n + 1);
  34.     for (int i = 1; i <= n; i++) {
  35.         cin >> P[i];
  36.     }
  37.  
  38.     order.resize(m);
  39.     for (int i = 0; i < m; i++) {
  40.         cin >> order[i];
  41.     }
  42.  
  43.     S.resize(q);
  44.     for (int i = 0; i < q; i++) {
  45.         cin >> S[i];
  46.     }
  47.  
  48.     string T;
  49.     for (int idx : order) {
  50.         T += P[idx];
  51.     }
  52.  
  53.     int T_len = T.size();
  54.  
  55.     for (int k = 0; k < q; k++) {
  56.         string& cur_S = S[k];
  57.         int s_len = cur_S.size();
  58.  
  59.         vector<vi> dp(s_len + 1, vi(T_len + 1, 0));
  60.  
  61.         for (int i = 1; i <= s_len; i++) {
  62.             for (int j = 1; j <= T_len; j++) {
  63.                 if (cur_S[i - 1] == T[j - 1]) {
  64.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  65.                 } else {
  66.                     dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  67.                 }
  68.             }
  69.         }
  70.  
  71.         cout << dp[s_len][T_len] << "\n";
  72.     }
  73. }
  74.  
  75. signed main() {
  76.     ios_base::sync_with_stdio(0);
  77.     cin.tie(0);
  78.     cout.tie(0);
  79.  
  80.     PROCESS();
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lZbAFx
language:
C++14 (gcc 8.3)
created:
3 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!