Find a Word

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;

string s[40];
ll ways[40][40];

char ans[1010];

pair<ll,ll> dbg[40][40];
ll mult[40][40];

int main() {
	int n;
	ll k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> s[i];
	ways[n-1][n-1] = 1;
	for (int i = n-1; i >= 0; i--) {
		for (int j = n-1; j >= 0; j--) {
			if (j == n-1 && i == n-1) continue;
			ways[i][j] = ways[i][j+1] + ways[i+1][j];
		}
	}
	
	map<pair<ll,ll>,set<pair<ll,pair<ll,ll>>>> old;
	old[{0,ways[0][0]}].emplace(1,pair<ll,ll>(0,0));--k;
	mult[0][0]=1;
	for (int diag = 0; diag < 2*n; diag++) {
		map<pair<ll,ll>,map<char,vector<pair<ll,pair<ll,ll>>>>> nw;
		for(auto& it: old){
			ll i,j;
			tie(i,j) = it.first;
			if(i>k || j<=k)continue;
			for(auto& jt : it.second){
				ll x,y,cnt;
				pair<ll,ll> coord;
				tie(cnt,coord) = jt;
				tie(x,y) = coord;
				dbg[x][y] = {i,j};
				ans[diag]=s[x][y];
				if(x+1<n)nw[{i,j}][s[x+1][y]].emplace_back(cnt,pair<ll,ll>(x+1,y));
				if(y+1<n)nw[{i,j}][s[x][y+1]].emplace_back(cnt,pair<ll,ll>(x,y+1));
			}
		}
		old.clear();
		for (auto& it : nw) {
			ll lasti;
			ll i,j;
			tie(i,j) = it.first;
			lasti=i;
			for(auto &jt:it.second){
				if(lasti>k)break;
				ll ni=lasti;
				for(auto& kt : jt.second){
					ll cnt,x,y;
					pair<ll,ll> coord;
					tie(cnt,coord) = kt;
					tie(x,y) = coord;
					ni+=ways[x][y]*cnt;
					mult[x][y]+=cnt;
				}
				if(ni>k){
					for(auto& kt : jt.second){
						ll cnt,x,y;
						pair<ll,ll> coord;
						tie(cnt,coord	) = kt;
						tie(x,y) = coord;
						old[{lasti,ni}].insert({mult[x][y],coord});
						dbg[x][y]={lasti,ni};
					}
					break;
				}
				lasti=ni;
			}
		}
	}
	//for(int i=0;i<n;++i){for(int j=0;j<n;++j)cout<<dbg[i][j].first<<','<<dbg[i][j].second<<' ';cout<<'\n';}
	//for(int i=0;i<n;++i){for(int j=0;j<n;++j)cout<<ways[i][j]<<' ';cout<<'\n';}
	cout<<ans<<endl;
}

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