oj.uz

Submission #703059

# Submission time Handle Problem Language Result Execution time Memory
703059 2023-02-25T20:21:12 Z rainboy K-th path (IZhO11_kthpath) C
100 / 100
 3 ms 224 KB 
#include <stdio.h>
#include <string.h>

#define N	30
#define M	30

int main() {
	static char cc[N][M + 1], aa[N + M];
	static long long dp[N][M][2];
	int n, m, h, i, j;
	long long k;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	scanf("%lld", &k);
	memset(aa, 'a', (n + m - 1) * sizeof *aa);
	for (h = 0; h < n + m - 1; h++) {
		for (aa[h] = 'a'; aa[h] <= 'z'; aa[h]++) {
			for (i = 0; i < n; i++)
				for (j = 0; j < m; j++)
					dp[i][j][0] = dp[i][j][1] = 0;
			if (cc[0][0] == aa[0])
				dp[0][0][0] = 1;
			else if (cc[0][0] < aa[0])
				dp[0][0][1] = 1;
			for (i = 0; i < n; i++)
				for (j = 0; j < m; j++) {
					long long x;

					if ((x = dp[i][j][0]) != 0) {
						if (i + 1 < n) {
							if (cc[i + 1][j] == aa[i + j + 1])
								dp[i + 1][j][0] += x;
							else if (cc[i + 1][j] < aa[i + j + 1])
								dp[i + 1][j][1] += x;
						}
						if (j + 1 < m) {
							if (cc[i][j + 1] == aa[i + j + 1])
								dp[i][j + 1][0] += x;
							else if (cc[i][j + 1] < aa[i + j + 1])
								dp[i][j + 1][1] += x;
						}
					}
					if ((x = dp[i][j][1]) != 0) {
						if (i + 1 < n)
							dp[i + 1][j][1] += x;
						if (j + 1 < m)
							dp[i][j + 1][1] += x;
					}
				}
			if (dp[n - 1][m - 1][1] >= k)
				break;
		}
		aa[h]--;
	}
	printf("%s\n", aa);
	return 0;
}

Compilation message

kthpath.c: In function 'main':
kthpath.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
kthpath.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~
kthpath.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%lld", &k);
      |  ^~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

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