Submission #432547

#	Time	Username	Problem	Language	Result	Execution time	Memory
432547		rainboy	Raisins (IOI09_raisins)	C11	100 / 100	142 ms	25444 KiB

raisins

#include <stdio.h>

#define N	50
#define M	50
#define INF	0x3f3f3f3f3f3f3f3f

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

int main() {
	static int aa[N + 1][M + 1];
	static long long dp[N][N][M][M];
	int n, m, i, j, il, jl, ir, jr;

	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			scanf("%d", &aa[i][j]);
	for (i = 0; i <= n; i++)
		for (j = 1; j <= m; j++)
			aa[i][j] += aa[i][j - 1];
	for (j = 0; j <= m; j++)
		for (i = 1; i <= n; i++)
			aa[i][j] += aa[i - 1][j];
	for (il = n - 1; il >= 0; il--)
		for (ir = il; ir < n; ir++)
			for (jl = m - 1; jl >= 0; jl--)
				for (jr = jl; jr < m; jr++)
					if (il < ir || jl < jr) {
						long long x = INF;

						for (i = il; i < ir; i++)
							x = min(x, dp[il][i][jl][jr] + dp[i + 1][ir][jl][jr]);
						for (j = jl; j < jr; j++)
							x = min(x, dp[il][ir][jl][j] + dp[il][ir][j + 1][jr]);
						dp[il][ir][jl][jr] = aa[ir + 1][jr + 1] - aa[ir + 1][jl] - aa[il][jr + 1] + aa[il][jl] + x;
					}
	printf("%lld\n", dp[0][n - 1][0][m - 1]);
	return 0;
}

Compilation message (stderr)

raisins.c: In function 'main':
raisins.c:14:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
raisins.c:17:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |    scanf("%d", &aa[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100