SHARE
TWEET

706-C

a guest Nov 12th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<map>
  3. using namespace std;
  4.  
  5. int n;
  6. const int N = 1e5 + 10;
  7. long long int INF = 1e9;
  8. long long int cost[N];
  9. string str[N];
  10.  
  11. map<string, map<int, bool>> viz;
  12. map<string, map<int, long long int>> dp;
  13.  
  14. string rev(string s){
  15.     string ans = "";
  16.     for(int i=s.size()-1; i >= 0; i--) ans += s[i];
  17.     return ans;
  18. }
  19.  
  20. long long int solve(string last, int i){
  21.     if(i >= n) return 0ll;
  22.    
  23.     if(viz[last][i]) return dp[last][i];
  24.  
  25.     int L = cost[i] + solve(rev(str[i]), i+1);
  26.     int R = solve(str[i], i+1);
  27.     if(last > str[i]) R = INF;
  28.     if(last > rev(str[i])) L = INF;
  29.    
  30.     viz[last][i] = true;
  31.     return dp[last][i] = min(L, R);
  32. }
  33.  
  34.  
  35. int main(){
  36.     cin >> n;
  37.     for(int i=0; i < n; i++) cin >> cost[i];
  38.     for(int i=0; i < n; i++) cin >> str[i];
  39.    
  40.     long long int ans = solve("a", 0ll);
  41.    
  42.     if(ans < INF) cout << ans << endl;
  43.     else cout << -1 << endl;
  44.  
  45. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top