Submission #930931

#	Time	Username	Problem	Language	Result	Execution time	Memory
930931		rainboy	L 모양의 종이 자르기 (KOI15_cut)	C11	25 / 25	254 ms	25688 KiB

cut

#include <stdio.h>

#define N	50
#define INF	0x3f3f3f3f

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

int dp[N + 1][N + 1], dq[N + 1][N + 1][N + 1][N + 1];

void init() {
	int x1, y1, x2, y2, x, y, z;

	for (x1 = 1; x1 <= N; x1++)
		for (y1 = 1; y1 <= N; y1++)
			if (x1 == y1)
				dp[x1][y1] = 1;
			else {
				z = INF;
				for (x = 1; x < x1; x++)
					z = min(z, dp[x][y1] + dp[x1 - x][y1]);
				for (y = 1; y < y1; y++)
					z = min(z, dp[x1][y] + dp[x1][y1 - y]);
				dp[x1][y1] = z;
			}
	for (x1 = 1; x1 <= N; x1++)
		for (y1 = 1; y1 <= N; y1++)
			for (x2 = 1; x2 < x1; x2++)
				for (y2 = 1; y2 < y1; y2++) {
					z = INF;
					for (x = 1; x < x1; x++)
						if (x < x2)
							z = min(z, dp[x][y1 - y2] + dq[x1 - x][y1][x2 - x][y2]);
						else if (x > x2)
							z = min(z, dq[x][y1][x2][y2] + dp[x1 - x][y1]);
						else
							z = min(z, dp[x2][y1 - y2] + dp[x1 - x2][y1]);
					for (y = 1; y < y1; y++)
						if (y < y2)
							z = min(z, dp[x1 - x2][y] + dq[x1][y1 - y][x2][y2 - y]);
						else if (y > y2)
							z = min(z, dq[x1][y][x2][y2] + dp[x1][y1 - y]);
						else
							z = min(z, dp[x1 - x2][y2] + dp[x1][y1 - y2]);
					dq[x1][y1][x2][y2] = z;
				}
}

int main() {
	int x1, y1, x2, y2;

	init();
	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
	printf("%d\n", dq[x1][y1][x2][y2]);
	return 0;
}

Compilation message (stderr)

cut.c: In function 'main':
cut.c:52:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25