Find a Word

#include <bits/stdc++.h>

using namespace std;
int n, k;
string s[33];
int64_t r[33][33];

string hae(string lol, int64_t k, int64_t a, int64_t b, int i, int j){
    if(k < a || k >= b)
        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];
            string re = hae(lol+s[i][j], k, a+ri, b, i+1, j);
            string re2 = hae(lol+s[i][j], k, a+down, b, i+1, j);
            string re3 = hae(lol+s[i][j], k, a, a+ri, i+1, j);
            string re4 = hae(lol+s[i][j], k, a, a+down, i+1, j);
            if(re.length() == 0){
                re = hae(lol+s[i][j], k, a, a+ri, i, j+1);
            }
            if(re2.length() == 0){
                re2 = hae(lol+s[i][j], k, a, a+down, i, j+1);
            }
            if(re3.length() == 0){
                re3 = hae(lol+s[i][j], k, a+ri, b, i, j+1);
            }
            if(re4.length() == 0){
                re4 = hae(lol+s[i][j], k, a+down, b, i, j+1);
            }
            if(re2.length() > re.length())
                re = re2;
            if(re3.length() > re.length())
                re = re3;
            if(re4.length() > re.length())
                re = re4;
            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(){
    cin >> n >> k;
    for(int i = 0; i < n; ++i)
        cin >> s[i];
    r[n-1][n-1] = 1;
    for(int i = n-1; i >= 0; --i){
        for(int j = n-1; j >= 0; --j){
            if(i < n-1)
                r[i][j] += r[i+1][j];
            if(j< n-1)
                r[i][j] += r[i][j+1];
        }
    }
    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: TIME LIMIT EXCEEDED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: TIME LIMIT EXCEEDED