fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4. #define pb emplace_back
  5. #define mp make_pair
  6. #define fi first
  7. #define se second
  8. #define all(v) v.begin(), v.end()
  9. #define ms(a, x) memset(a, x, sizeof(a));
  10.  
  11. int n;
  12. string s[100009];
  13. int a[100009];
  14. map<pair<int, string>, int> dp;
  15.  
  16. int solve(int i, string prev)
  17. {
  18.     if (i >= n)
  19.         return 0;
  20.  
  21.     if (dp.find({i, prev}) != dp.end())
  22.     {
  23.         return dp[{i, prev}];
  24.     }
  25.  
  26.     int x1 = 1e16, x2 = 1e16;
  27.     if (s[i] >= prev)
  28.         x1 = solve(i + 1, s[i]);
  29.     string s1 = s[i];
  30.     reverse(all(s1));
  31.     if (s1 >= prev)
  32.         x2 = a[i] + solve(i + 1, s1);
  33.  
  34.     return dp[{i, prev}] = min(x1, x2);
  35. }
  36.  
  37. signed main()
  38. {
  39.  
  40.     int i, x;
  41.     ms(a, 0);
  42.     cin >> n;
  43.     for (i = 0; i < n; i++)
  44.         cin >> a[i];
  45.  
  46.     for (i = 0; i < n; i++)
  47.         cin >> s[i];
  48.     string ss = "A";
  49.  
  50.     x = solve(0, ss);
  51.     if (x >= 1e16)
  52.         x = -1;
  53.  
  54.     cout << x;
  55. }
Success #stdin #stdout 0.01s 7420KB
comments (?)
stdin
copy 
2
1 2
ba
ac
stdout
copy 
1
https://ideone.com/X6Yv5P
language:
C++14 (gcc 8.3)
created:
2 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!