Find a Word

#include <bits/stdc++.h>
 
using namespace std;
int n;
string s[33];
int64_t r[33][33];
string pp[33][33];
int np[33][33];
string hae(string lol, int64_t k, int64_t a, int64_t b, int i, int j){
    //cout << lol+s[i][j] << " " << k << " " << a << " " << b << " " << i << " " << j << " " << np[i][j] << " " <<pp[i][j] << endl;
    if(k < a || k >= b){
       // cout << "re1" << endl;
        return "";
    }
    if(i == n-1 && j == n-1){
        if(k >= a && k < b)
            return lol+s[i][j];
        return "";
    }
        
    if(i < n-1 && j < n-1){
        if(s[i+1][j] < s[i][j+1]){
            int down = r[i+1][j];
            string re = hae(lol+s[i][j], k, a, a+down, i+1, j);
            if(re.length() == 0){
                re = hae(lol+s[i][j], k, a+down, b, i, j+1);
            }
            return re;
        }
        else if(s[i+1][j] > s[i][j+1]){
            int ri = r[i][j+1];
            string re = hae(lol+s[i][j], k, a+ri, b, i+1, j);
            if(re.length() == 0){
                re = hae(lol+s[i][j], k, a, a+ri, i, j+1);
            }
            return re;
        }
        else {
            int ri = r[i][j+1];
            int down = r[i+1][j];
            if(np[i][j] == 1){
                string re3 = hae(lol+s[i][j], k, a, a+down, i+1, j);
                if(re3.length() == 0){
                    re3 = hae(lol+s[i][j], k, a+down, b, i, j+1);
                }
                return re3;
            }
            else {
                string re = hae(lol+s[i][j], k, a+ri, b, i+1, j);
                if(re.length() == 0){
                    re = hae(lol+s[i][j], k, a, a+ri, i, j+1);
                }
                return re;
            }
        }
    }
    else if(i < n-1){
        return hae(lol+s[i][j], k, a, b, i+1, j);
    }
    else if(j < n-1){
        return hae(lol+s[i][j], k, a, b, i, j+1);
    }
    return "";
}
 
 
int main(){
    int k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i)
        cin >> s[i];
    r[n-1][n-1] = 1;
    pp[n-1][n-1] = s[n-1][n-1];
    for(int i = n-1; i >= 0; --i){
        for(int j = n-1; j >= 0; --j){
            string c1 = "0";
            c1[0] = 'Z'+1;
            string c2 = "0";
            c2[0] = 'Z'+1;
            if(i < n-1){
                r[i][j] += r[i+1][j];
                c1 = s[i][j]+pp[i+1][j];
            }
            if(j< n-1){
                r[i][j] += r[i][j+1];
                c2 = s[i][j]+pp[i][j+1];
            }
            if(i < n-1 || j < n-1){
                if(c1 < c2){
                    np[i][j] = 1;
                    pp[i][j] = c1;
                }
                else{
                    pp[i][j] = c2;
                }
            }
            //cout << i << " " << j << " " << pp[i][j] << endl;
        }
    }
    cout << hae("", k-1, 0, r[0][0], 0, 0) << endl;
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER