fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define endl '\n'
  4. #define ll long long
  5. #define all(a) a.begin(),a.end()
  6. #define ld long double
  7. using namespace std;
  8.  
  9. void Tamora() {
  10.     ios_base::sync_with_stdio(0);
  11.     cin.tie(0);
  12.     cout.tie(0);
  13.     freopen("transform.in", "r", stdin);
  14.  
  15. #ifndef ONLINE_JUDGE
  16.     freopen("input.txt", "r", stdin);
  17.     freopen("output.txt", "w", stdout);
  18. #endif
  19.  
  20. }
  21.  
  22. const ll mod = 1e9 + 7, inf = 1e17 + 5, N = 2e3 + 5, M = 1e4 + 7, LG = 25, P1 = 37, P2 = 31;
  23.  
  24. int n, m, a[N], b[N], c[N], first[N], last[N], vid, vis[N][N];
  25. ll suf[N], dp[N][N];
  26.  
  27. ll calc(int i, int j) {
  28.     if (j == m)return suf[i];
  29.     if (i == n)return inf;
  30.     ll &ret = dp[i][j];
  31.     if (vis[i][j] == vid)
  32.         return ret;
  33.     vis[i][j] = vid;
  34.     ret = inf;
  35.     if (a[i] == b[j])
  36.         ret = calc(i + 1, j + 1);
  37.     if (first[a[i]] == -1 || j <= first[a[i]] || last[a[i]] < j)
  38.         ret = min(ret, calc(i + 1, j) + c[i]);
  39.     return ret;
  40. }
  41.  
  42. void solve() {
  43.     vid++;
  44.     cin >> n >> m;
  45.     vector<int> v;
  46.     for (int i = 0; i < n; i++)
  47.         cin >> a[i], v.push_back(a[i]);
  48.     for (int i = 0; i < m; i++)
  49.         cin >> b[i], v.push_back(b[i]);
  50.     sort(all(v));
  51.     v.erase(unique(all(v)), v.end());
  52.     for (int i = 0; i < v.size(); i++)
  53.         first[i] = last[i] = -1;
  54.     for (int i = 0; i < n; i++)
  55.         a[i] = lower_bound(all(v), a[i]) - v.begin();
  56.     for (int i = 0; i < m; i++) {
  57.         b[i] = lower_bound(all(v), b[i]) - v.begin();
  58.         if (!~first[b[i]])first[b[i]] = i;
  59.         last[b[i]] = i;
  60.     }
  61.     for (int i = 0; i < n; i++)
  62.         cin >> c[i];
  63.     suf[n] = 0;
  64.     for (int i = n - 1; i >= 0; i--)
  65.         suf[i] = suf[i + 1] + c[i];
  66.     ll ans = calc(0, 0);
  67.     if (ans >= 1e16)
  68.         return void(cout << "No" << endl);
  69.     cout << ans << endl;
  70. }
  71.  
  72. int main() {
  73.     Tamora();
  74.     int t = 1;
  75.     cin >> t;
  76.     for (int i = 1; i <= t; i++)
  77.         solve();
  78.     return 0;
  79. }
  80.  
  81.  
  82.  
Success #stdin #stdout 0.01s 5720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/8pCjQS
language:
C++ (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!