oj.uz

Submission #930931

# Submission time Handle Problem Language Result Execution time Memory
930931 2024-02-20T20:27:57 Z rainboy L 모양의 종이 자르기 (KOI15_cut) C
25 / 25
 254 ms 25688 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 209 ms 25680 KB Output is correct
2 Correct 211 ms 25556 KB Output is correct
3 Correct 213 ms 25688 KB Output is correct
4 Correct 239 ms 25568 KB Output is correct
5 Correct 217 ms 25576 KB Output is correct
6 Correct 222 ms 25580 KB Output is correct
7 Correct 210 ms 25684 KB Output is correct
8 Correct 207 ms 25684 KB Output is correct
9 Correct 232 ms 25584 KB Output is correct
10 Correct 212 ms 25580 KB Output is correct
11 Correct 223 ms 25588 KB Output is correct
12 Correct 212 ms 25680 KB Output is correct
13 Correct 221 ms 25680 KB Output is correct
14 Correct 216 ms 25564 KB Output is correct
15 Correct 254 ms 25572 KB Output is correct
16 Correct 208 ms 25576 KB Output is correct
17 Correct 252 ms 25580 KB Output is correct
18 Correct 217 ms 25680 KB Output is correct
19 Correct 212 ms 25572 KB Output is correct
20 Correct 206 ms 25580 KB Output is correct