fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long INF = 1e18;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(NULL);
  9.  
  10.     int n, k;
  11.     if (!(cin >> n >> k)) return 0;
  12.  
  13.     vector<int> a(n + 1);
  14.     vector<int> l(k + 1), s(k + 1);
  15.  
  16.     for (int i = 1; i <= n; i++) cin >> a[i];
  17.     for (int i = 1; i <= k; i++) cin >> l[i];
  18.     for (int i = 1; i <= k; i++) cin >> s[i];
  19.  
  20.     vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, INF));
  21.  
  22.     dp[0][0] = 0;
  23.  
  24.     for (int i = 0; i <= n; i++) {
  25.         for (int j = 0; j <= n; j++) {
  26.             if (dp[i][j] == INF) continue;
  27.  
  28.             int st = max(i, j) + 1;
  29.             if (st > n) continue;
  30.  
  31.             int type = a[st];
  32.  
  33.             int A;
  34.             if (i == 0) A = l[type];
  35.             else A = (a[i] == type) ? s[type] : l[type];
  36.  
  37.             dp[st][j] = min(dp[st][j], dp[i][j] + A);
  38.  
  39.             int B;
  40.             if (j == 0) B = l[type];
  41.             else B = (a[j] == type) ? s[type] : l[type];
  42.  
  43.             dp[i][st] = min(dp[i][st], dp[i][j] + B);
  44.         }
  45.     }
  46.  
  47.     long long ans = INF;
  48.     for (int i = 0; i <= n; i++) {
  49.         ans = min({ans, dp[n][i], dp[i][n]});
  50.     }
  51.  
  52.     cout << ans << endl;
  53.  
  54.     return 0;
  55. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CseXfq
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!