oj.uz

Submission #477039

# Submission time Handle Problem Language Result Execution time Memory
477039 2021-09-29T21:59:21 Z rainboy Maja (COCI18_maja) C
110 / 110
 493 ms 376 KB 
#include <stdio.h>
#include <string.h>

#define N	100
#define M	100
#define K	10100

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_));
			}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 204 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 204 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 292 KB Output is correct
2 Correct 12 ms 296 KB Output is correct
3 Correct 325 ms 368 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 204 KB Output is correct
2 Correct 395 ms 352 KB Output is correct
3 Correct 341 ms 376 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 364 KB Output is correct
2 Correct 493 ms 368 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 296 KB Output is correct
2 Correct 118 ms 332 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 284 KB Output is correct
2 Correct 26 ms 332 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 352 KB Output is correct
2 Correct 23 ms 204 KB Output is correct