Code Submission Evaluation System Login

CSES - HIIT Open 2018

HIIT Open 2018

Contest start:2018-05-26 11:00:00
Contest end:2018-05-26 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2018-05-26 12:03:13
Task:Find a Word
Sender:Ukkonen Fan Club
Submission time:2018-05-26 12:03:13
Status:READY
Result:ACCEPTED

Show test data

Code

#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';
}