C_Hard_Problem

help
, ,
1

Question

#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define vi vector<int>
#define vb vector<bool>
#define vd vector<double>
#define vc vector<char>
#define vii vector<vi>
#define mp make_pair
#define vpi vector< pair<int, int> >
#define take_input freopen("input.txt", "r", stdin)
#define give_output freopen("output.txt", "w", stdout)
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fi first
#define se second
#define mod 1e9+7
#define min_pql priority_queue< int, vector<int>, greater<int> >

using namespace std;
using namespace std::chrono;

int32_t main(){
    fastIO;
    int n; cin >> n;
    vi energy(n);
    for(int &i:energy) cin >> i;
    vector<string> str(n);
	for(string &i:str) cin >> i;
	vii dp(n, vi(2, mod));
	string rstr1, rstr2; bool f1=true, f2=true;
	rstr1 = string(str[0].rbegin(), str[0].rend());
	dp[0][0] = 0; dp[0][1] = energy[0];
	for(int i=1; i<n; i++){
		rstr2 = string(str[i].rbegin(), str[i].rend());
		if(str[i]>str[i-1] && str[i]>rstr1){
			dp[i][0] = min(dp[i-1][0], dp[i-1][1]);
		}else if(str[i]>str[i-1] && dp[i-1][0] != mod){
			dp[i][0] = dp[i-1][0];
		}else if(str[i]>rstr1 && dp[i-1][1] != mod){
			dp[i][0] = dp[i-1][1];
		}else{
			f1 = false;
		}

		if(rstr2>str[i-1] && rstr2>rstr1){
			dp[i][1] = min(dp[i-1][0], dp[i-1][1])+energy[i];
		}else if(rstr2>str[i-1] && dp[i-1][0] != mod){
			dp[i][1] = dp[i-1][0]+energy[i];
		}else if(rstr2>rstr1 && dp[i-1][1] != mod){
			dp[i][1] = dp[i-1][1]+energy[i];
		}else if(!f1){
			f2 = false;
			break;
		}
		f1 = true;
		rstr1 = rstr2;
	}
	if(f1 && f2){
		cout << min(dp[n-1][1], dp[n-1][0]) << endl;
	}else{
		cout << -1 << endl;
	}
}

Can somebody suggest what I am missing in this code. I am not able to clear all the test cases

2

You can check it here I have solved it using memomization

3

Thanks for your approach
But can you please also see to my code and suggest what I am doing wrong.