Submission #28054

#	Time	Username	Problem	Language	Result	Execution time	Memory
28054		undecember	L 모양의 종이 자르기 (KOI15_cut)	C++14	25 / 25	293 ms	28444 KiB

cut

#include <bits/stdc++.h>

using namespace std;

int ddp[51][51][51][51]; //h1, w1, h2, w2
int h1, w1, h2, w2;

int dp(int H, int W, int h, int w);

int main(void)
{
	scanf("%d%d%d%d", &h1, &w1, &h2, &w2);

	memset(ddp, -1, sizeof(ddp));

	printf("%d", dp(h1, w1, h2, w2));
	return 0;
}

int dp(int H, int W, int h, int w)
{
	if (ddp[H][W][h][w] >= 0) return ddp[H][W][h][w];
	if (h == 0 ^ w == 0) return dp(H, W, 0, 0);
	if (H == W && h == 0 && w == 0)
	{
		ddp[H][W][h][w] = 1;
		return 1;
	}

	int ans = INT_MAX;

	int i;
	for (i = 1; i < W - w; i++)
		ans = min(ans, dp(H, i, 0, 0) + dp(H, W - i, h, w));
	for (i; i < W; i++)
		ans = min(ans, dp(H, i, h, i - (W - w)) + dp(H - h, W - i, 0, 0));

	for (i = 1; i < H - h; i++)
		ans = min(ans, dp(i, W, 0, 0) + dp(H - i, W, h, w));
	for (i; i < H; i++)
		ans = min(ans, dp(i, W, i - (H - h), w) + dp(H - i, W - w, 0, 0));

	ddp[H][W][h][w] = ans;
	return ans;
}

Compilation message (stderr)

cut.cpp: In function 'int dp(int, int, int, int)':
cut.cpp:23:8: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  if (h == 0 ^ w == 0) return dp(H, W, 0, 0);
        ^
cut.cpp:35:8: warning: statement has no effect [-Wunused-value]
  for (i; i < W; i++)
        ^
cut.cpp:40:8: warning: statement has no effect [-Wunused-value]
  for (i; i < H; i++)
        ^
cut.cpp: In function 'int main()':
cut.cpp:12:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &h1, &w1, &h2, &w2);
                                       ^

• Subtask 1: 25 / 25