Submission #477032

#	Time	Username	Problem	Language	Result	Execution time	Memory
477032		rainboy	Maja (COCI18_maja)	C11	44 / 110	1495 ms	408 KiB

maja

#include <stdio.h>
#include <string.h>

#define N	100
#define M	100
#define K	40404

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

int min(int a, int b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

int main() {
	static int aa[N][M];
	static long long dp[N][M];
	int n, m, k, k_, h, i, j, is, js, l;
	long long ans;

	scanf("%d%d%d%d%d", &n, &m, &is, &js, &k), is--, js--, k /= 2;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &aa[i][j]);
	for (i = 0; i < n; i++)
		memset(dp[i], -1, m * sizeof *dp[i]);
	dp[is][js] = aa[is][js];
	ans = 0;
	k_ = min(k, k % 2 == 0 ? K : K + 1);
	for (l = 1; l <= k_; l++)
		for (i = 0; i < n; i++)
			for (j = 0; j < m; j++)
				if ((i + is + j + js + l) % 2 == 0) {
					long long x = -1;

					for (h = 0; h < 4; h++) {
						int i_ = i + di[h], j_ = j + dj[h];

						if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && dp[i_][j_] != -1)
							x = max(x, dp[i_][j_] + aa[i][j]);
					}
					dp[i][j] = x;
				}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if ((i + is + j + js + k) % 2 == 0 && dp[i][j] != -1) {
				int a = 0;

				for (h = 0; h < 4; h++) {
					int i_ = i + di[h], j_ = j + dj[h];

					if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m)
						a = max(a, aa[i_][j_]);
				}
				ans = max(ans, dp[i][j] * 2 - aa[i][j] + (long long) (aa[i][j] + a) * (k - k_) / 2);
			}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

maja.c: In function 'main':
maja.c:20:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d%d%d%d%d", &n, &m, &is, &js, &k), is--, js--, k /= 2;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
maja.c:23:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |    scanf("%d", &aa[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11