Codeforces Round #367 (Div. 2) C. Hard problem - dblank

# Codeforces Round #367 (Div. 2) C. Hard problem

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10, pi = acos(-1.0);
const int inf = 0x3f3f3f3f, N = 100000 + 200, Mod = 110119;
typedef long long  ll;
vector<string> s;
int a[N], l[N];
ll dp[N][2];
int main()
{
int n;
while(cin>>n)
{
string str;
memset(dp, 0x3f, sizeof(dp));
s.clear();
for(int i = 0; i<n; i++)
scanf("%d", &a[i]);
for(int i = 1; i<=n; i++)
{
cin>>str;
s.push_back(str);
}
string x, y;
dp[0][1] = a[0];
dp[0][0] = 0;
for(int i = 1; i<s.size(); i++)
{
x = s[i-1];
y = s[i];
reverse(x.begin(), x.end());
reverse(y.begin(), y.end());
if(s[i-1]<=s[i]) dp[i][0] = min(dp[i][0], dp[i-1][0]);
if(x <= s[i]) dp[i][0] = min(dp[i-1][1], dp[i][0]);
if(y >= s[i-1]) dp[i][1] = min(dp[i][1], dp[i-1][0] + a[i]);
if(y >= x) dp[i][1] = min(dp[i-1][1] + a[i], dp[i][1]);
}
ll ans = min(dp[n-1][1], dp[n-1][0]);
if(ans == dp[N-1][1])
printf("-1\n");
else printf("%lld\n", ans);
}
return 0;
}