fork download
copy 
  1. #include<bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp> // Common file
  3. //#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4.  
  5. using namespace std;
  6. //using namespace __gnu_pbds;
  7. //typedef tree<
  8. //        pair<long long, int>, // change type
  9. //        null_type,
  10. //        less<pair<long long, int> >, // change type
  11. //        rb_tree_tag,
  12. //        tree_order_statistics_node_update>
  13. //        ordered_set;
  14.  
  15. typedef long long ll;
  16. #define rep(i, start, end) for(int i = start; i < end; ++i)
  17. #define sz(x) (int)(x).size()
  18. #define pb push_back
  19. #define row first
  20. #define col second
  21. #define all(x) x.begin(), x.end()
  22. #define clr(d, v) memset(d, v, sizeof(d))
  23. #define pii pair<int, int>
  24. const double PI = 3.14159265358979323846;
  25. const double eps = (1e-4);
  26. int dcmp(long double x, long double y)
  27. {
  28.     if (abs(x - y) < eps)
  29.         return 0;
  30.     if (x > y)
  31.         return 1;
  32.     return -1;
  33. }
  34.  
  35.  
  36. map<int, int> after;
  37. int n, m;
  38. const int MAX_N = 2005;
  39. ll mem[MAX_N][MAX_N];
  40. int visit[MAX_N][MAX_N], vid;
  41. int a[MAX_N], b[MAX_N], c[MAX_N], cpr[2 * MAX_N];
  42. bool existL[MAX_N][MAX_N], existR[MAX_N][MAX_N];
  43.  
  44.  
  45. ll solve(int i, int j)
  46. {
  47.     if (i == n && j == m)
  48.         return 0;
  49.     if (i == n)
  50.         return (1LL<<50);
  51.     ll &ret = mem[i][j];
  52.     if (visit[i][j] == vid)
  53.         return ret;
  54.     visit[i][j] = vid;
  55.     ret = (1LL<<50);
  56.     // match
  57.     if (j < m && a[i] == b[j])
  58.         ret = min(ret, solve(i + 1, j + 1));
  59.     // delete with no left
  60.     if (!existL[j][a[i]])
  61.         ret = min(ret, solve(i + 1, j) + c[i]);
  62.     // delete with no right
  63.     if (!existR[j][a[i]])
  64.         ret = min(ret, solve(i + 1,j) + c[i]);
  65.     return ret;
  66. }
  67.  
  68.  
  69. void clear()
  70. {
  71.     ++vid;
  72.     clr(mem, -1);
  73.     clr(existL, 0);
  74.     clr(existR, 0);
  75.     after.clear();
  76. }
  77.  
  78. int main()
  79. {
  80.     ios_base::sync_with_stdio(false);
  81.     cin.tie(0);
  82.     cout.tie(0);
  83. #ifndef ONLINE_JUDGE
  84.     freopen("input.txt", "r", stdin);
  85. //    freopen("facebook.txt", "w", stdout);
  86. #endif
  87.     freopen("transform.in", "r", stdin);
  88.     int tc;
  89.     cin >> tc;
  90.     while(tc--)
  91.     {
  92.         cin >> n >> m;
  93.         clear();
  94.         int cnt = 0;
  95.         rep(i,0,n)
  96.         {
  97.             cin >> a[i];
  98.             cpr[cnt++] = a[i];
  99.         }
  100.         rep(i,0,m)
  101.         {
  102.             cin >> b[i];
  103.             cpr[cnt++] = b[i];
  104.         }
  105.         rep(i,0,n)
  106.             cin >> c[i];
  107.  
  108.         sort(cpr, cpr + cnt);
  109.         int id = 0;
  110.         for (int i = 0; i < cnt; ++i)
  111.         {
  112.             auto it = after.find(cpr[i]);
  113.             if (it == after.end())
  114.                 after[cpr[i]] = id++;
  115.         }
  116.  
  117.         for (int i = 0; i < n; ++i)
  118.             a[i] = after[a[i]];
  119.         for (int i = 0; i < m; ++i)
  120.             b[i] = after[b[i]];
  121.  
  122.  
  123.         for (int i = 0; i < m; ++i)
  124.         {
  125.             for (int j = i + 1; j <= m; ++j)
  126.                 existL[j][b[i]] = 1;
  127.         }
  128.  
  129.         for (int i = m - 1; i >= 0; --i)
  130.         {
  131.             for (int j = i; j >= 0; --j)
  132.                 existR[j][b[i]] = 1;
  133.         }
  134.  
  135.         ll ans = solve(0, 0);
  136.         if (ans >= (1LL<<49))
  137.             cout << "No";
  138.         else
  139.             cout << ans;
  140.         cout << '\n';
  141.     }
  142.  
  143.     return 0;
  144. }
Runtime error #stdin #stdout #stderr 0s 70272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/k6GHKd
language:
C++14 (gcc 8.3)
created:
5 years 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!