oj.uz

Submission #93707

# Submission time Handle Problem Language Result Execution time Memory
93707 2019-01-10T19:39:50 Z Noam527 K-th path (IZhO11_kthpath) C++17
100 / 100
 3 ms 504 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 ms 380 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct