Submission #703059

#	Time	Username	Problem	Language	Result	Execution time	Memory
703059		rainboy	K-th path (IZhO11_kthpath)	C11	100 / 100	3 ms	224 KiB

kthpath

#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 (stderr)

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 / 100