oj.uz

Submission #477032

# Submission time Handle Problem Language Result Execution time Memory
477032 2021-09-29T21:03:51 Z rainboy Maja (COCI18_maja) C
44 / 110
 1495 ms 408 KB 
#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

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 280 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 5 ms 204 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 589 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1495 ms 408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 533 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 455 ms 368 KB Output isn't correct
2 Halted 0 ms 0 KB -