Submission #93707

#	Time	Username	Problem	Language	Result	Execution time	Memory
93707		Noam527	K-th path (IZhO11_kthpath)	C++17	100 / 100	3 ms	504 KiB

kthpath

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' ' && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

int n, m;
ll k;
string s[30];
ll dp[30][30][2];

bool can(string &x) {
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) dp[i][j][0] = dp[i][j][1] = 0;
	if (x[0] > s[0][0]) dp[0][0][1] = 1;
	else if (x[0] == s[0][0]) dp[0][0][0] = 1;
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		if (i | j) {
			if (x[i + j] > s[i][j]) {
				if (i > 0) dp[i][j][1] += dp[i - 1][j][1] + dp[i - 1][j][0];
				if (j > 0) dp[i][j][1] += dp[i][j - 1][1] + dp[i][j - 1][0];
			}
			else {
				if (i > 0) {
					if (x[i + j] == s[i][j]) dp[i][j][0] += dp[i - 1][j][0];
					dp[i][j][1] += dp[i - 1][j][1];
				}
				if (j > 0) {
					if (x[i + j] == s[i][j]) dp[i][j][0] += dp[i][j - 1][0];
					dp[i][j][1] += dp[i][j - 1][1];
				}
			}
			dp[i][j][0] = min(dp[i][j][0], k);
			dp[i][j][1] = min(dp[i][j][1], k);
		}
	}
	return dp[n - 1][m - 1][0] + dp[n - 1][m - 1][1] >= k;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> s[i];
	cin >> k;
	string ans(n + m - 1, 'z');
	for (int i = 0; i < n + m - 1; i++) {
		char lo = 'a', hi = 'z', mid;
		while (lo < hi) {
			mid = (lo + hi) / 2;
			ans[i] = mid;
			if (can(ans)) hi = mid;
			else lo = mid + 1;
		}
		ans[i] = lo;
	}
	finish(ans);
}

• Subtask 1: 100 / 100