fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll INF=1e18;
  5. int main() {
  6.  
  7.     int n;
  8.     cin>>n;
  9.     vector<int>penalty(n);
  10.     for(int i=0;i<n;i++){
  11.         cin>>penalty[i];
  12.     }
  13.     vector<string>s(n),rev(n);
  14.     for(int i=0;i<n;i++){
  15.         cin>>s[i];
  16.         rev[i]=s[i];
  17.         reverse(rev.begin(),rev.end());
  18.     }
  19.     vector<vector<ll>>dp(n,vector<ll>(2,INF));
  20.     dp[0][0]=0;
  21.     dp[0][1]=penalty[0];
  22.     for(int i=1;i<n;i++){
  23.         if(s[i]>=s[i-1]){
  24.             dp[i][0]=min(dp[i-1][0],dp[i][0]);
  25.         }
  26.         if(s[i]>=rev[i-1]){
  27.             dp[i][0]=min(dp[i-1][1],dp[i][0]);
  28.         }        
  29.         if(rev[i]>=s[i-1]){
  30.             dp[i][1]=min(dp[i-1][0],dp[i][1])+penalty[i];
  31.         }        
  32.         if(rev[i]>=rev[i-1]){
  33.             dp[i][1]=min(dp[i-1][1],dp[i][1])+penalty[i];
  34.         }
  35.     }
  36.     ll ans=min(dp[n-1][0],dp[n-1][1]);
  37.     if(ans!=INF){
  38.         cout<<ans<<endl;
  39.     }
  40.     else cout<<-1<<endl;
  41. }
  42.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
1 2
ba
ac
stdout
copy 
1
https://ideone.com/nKzvKb
language:
C++14 (gcc 8.3)
created:
1 day 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!