# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
56675315 |
Practice:
imaking |
706C
- 57
|
C++14 (GCC 6-32)
|
Wrong answer on test 8
|
78 ms
|
3080 KB
|
2019-07-07 18:11:32 |
2019-07-07 18:11:32 |
|
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
// your code goes here
int n;
cin>>n;
long long int cost[n];
for(int i=0;i<n;i++){
cin>>cost[i];
}
//cout<<cost[0];
string str[n];
string strR[n];
for(int i=0;i<n;i++){
cin>>str[i];
}
long long int dp[n][2];
dp[0][0]=0;
dp[0][1]=cost[0];
//cout<<dp[0][0]<< " "<< dp[0][1]<<"\n";
strR[0]=str[0];
reverse((strR[0]).begin() , (strR[0]).end());
for(int i=1;i<n;i++){
int flag0=0, flag1=0;
if(str[i]>=str[i-1] && dp[i-1][0] != -1)
{ dp[i][0]=dp[i-1][0]; flag0=1; }
if(str[i]>=strR[i-1] && dp[i-1][1] != -1)
{ dp[i][0]=min(dp[i][0],dp[i-1][1]); flag0=1; }
strR[i]=str[i];
reverse((strR[i]).begin() , (strR[i]).end());
if(strR[i] >= str[i-1] && dp[i-1][0] != -1)
{dp[i][1]= dp[i-1][0] + cost[i]; flag1=1;}
if(strR[i] >= strR[i-1] && dp[i-1][1] != -1)
{dp[i][1] = min(dp[i][1], (dp[i-1][1] +cost[i])); flag1=1; }
if(flag0==0)
dp[i][0]= -1;
if(flag1==0)
dp[i][1]= -1;
}
/*
for(int i=0;i<n;i++){
cout<<dp[i][0] <<" "<< dp[i][1]<<"\n";
}
*/
if(dp[n-1][0] >= 0 && dp[n-1][1]>= 0)
cout<<min(dp[n-1][0], dp[n-1][1])<<"\n";
else{
if(dp[n-1][0]<0 && dp[n-1][1]>=0)
cout<<dp[n-1][1]<<"\n";
if(dp[n-1][0]>=0 && dp[n-1][1]<0)
cout<<dp[n-1][0]<<"\n";
if(dp[n-1][0]<0 && dp[n-1][1]<0)
cout<<"-1\n";
}
return 0;
}
Click to see test details