Find a Word

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll dp[40][40];
ll dp2[40][40];
char t[40][40];
int main() {
	ll n,k;
	cin>>n>>k;
	dp[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 && j == n-1) continue;
			dp[i][j] = dp[i+1][j] + dp[i][j+1];
		}
	}
	/*
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			cout<<dp[i][j]<<' ';
		}
		cout<<'\n';
	}
	*/
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			cin>>t[i][j];
		}
	}
	string res;;
	for(int i = 0; i < n+n-1; ++i) res.push_back('.');
	ll cnt = 0;
	for(int pos = 0; pos < n+n-1; ++pos) {
		ll mahd = 0;
		//cout<<pos<<'\n';
		for(int c = 'A'; c <= 'Z'; ++c) {
			res[pos] = c;
			memset(dp2, 0, sizeof dp2);
			for(int i = 0; i < n; ++i) {
				for(int j = 0; j < n; ++j) {
					if(t[i][j] != res[i+j]) {
						continue;
					}
					if(i == 0 && j == 0) {
						dp2[i][j] = 1;
					}
					if(i > 0) {
						dp2[i][j] += dp2[i-1][j];
					}
					if(j > 0) {
						dp2[i][j] += dp2[i][j-1];
					}
				}
			}
			ll more = 0;
			for(int i = 0; i < n; ++i) {
				for(int j = 0; j < n; ++j) {
					//cout<<dp2[i][j]<<' ';
					if(i+j == pos) {
						more += dp2[i][j] * dp[i][j];
					}
				}
				//cout<<'\n';
			}
			//cout<<'\n';
			//cout<<mahd<<' '<<more<<'\n';
			if(mahd + more + cnt >= k) {
				cnt += mahd;
				break;
			}
			mahd += more;
		}
	}
	cout<<res<<'\n';
}

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: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED