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:27:24
2018-05-26 12:19:40
Task:Find a Word
Sender:Karhukopla
Submission time:2018-05-26 12:27:24
Status:READY
Result:ACCEPTED

Show test data

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ans.length() != 2 * n - 1) ans.push_back('Z');
         ~~~~~~~~~~~~~^~~~~~~~~~~~

Code

#include <bits/stdc++.h>

#define ll long long
#define lll __int128
#define pii pair<int, int>
#define M 1000000007
#define N 30
using namespace std;

lll dp[N][N];
lll eq[N][N];
char c[N][N];

int main () {
	ll n, kk;
	cin>>n>>kk;
	lll k = kk;
	string ans;
	
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) cin>>c[y][x];
	}
	
	while (ans.length() != 2 * n - 1) ans.push_back('Z');
	for (int i = 0; i < 2 * n - 1; i++) {
		bool b = true;
		while (b) {
			for (int y = 0; y < n; y++) {
				for (int x = 0; x < n; x++) eq[y][x] = dp[y][x] = 0;
			}
			for (int y = 0; y < n; y++) {
				for (int x = 0; x < n; x++) {
					int p = y + x;
					if (c[y][x] < ans[p]) {
						if (p == 0) {
							dp[y][x] = 1;
							eq[y][x] = 0;
						} else if (!y) {
							dp[y][x] = dp[y][x - 1] + eq[y][x - 1];
							eq[y][x] = 0;
						} else if (!x) {
							dp[y][x] = dp[y - 1][x] + eq[y - 1][x];
							eq[y][x] = 0;
						} else {
							dp[y][x] = dp[y - 1][x] + dp[y][x - 1] + eq[y - 1][x] + eq[y][x - 1];
							eq[y][x] = 0;
						}
					} else if (c[y][x] == ans[p]) {
						if (p == 0) {
							dp[y][x] = 0;
							eq[y][x] = 1;
						} else if (!y) {
							dp[y][x] = dp[y][x - 1];
							eq[y][x] = eq[y][x - 1];
						} else if (!x) {
							dp[y][x] = dp[y - 1][x];
							eq[y][x] = eq[y - 1][x];
						} else {
							dp[y][x] = dp[y - 1][x] + dp[y][x - 1];
							eq[y][x] = eq[y - 1][x] + eq[y][x - 1];
						}
					} else if (c[y][x] > ans[p]) {
						if (p == 0) {
							dp[y][x] = 0;
							eq[y][x] = 0;
						} else if (!y) {
							dp[y][x] = dp[y][x - 1];
							eq[y][x] = 0;
						} else if (!x) {
							dp[y][x] = dp[y - 1][x];
							eq[y][x] = 0;
						} else {
							dp[y][x] = dp[y - 1][x] + dp[y][x - 1];
							eq[y][x] = 0;
						}
					}
				}
			}
			if (dp[n - 1][n - 1] + eq[n - 1][n - 1] >= k) ans[i]--;
			else break;
		}
		ans[i]++;
	}
	cout<<ans<<endl;
}

/**
AAU
YBA
BTY
*/