제출 #26005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26005		kajebiii	L 모양의 종이 자르기 (KOI15_cut)	C++14	25 / 25	443 ms	37776 KiB

cut

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 55;

int A, B, C, D;
int Dy[MAX_N][MAX_N][MAX_N][MAX_N], R[MAX_N][MAX_N];

void push(int &a, int b) {
	a = min(a, b);
}
int main() {
	cin >> A >> B >> C >> D;
	for(int a=1; a<=A; a++) for(int b=1; b<=B; b++) {
		if(a == b) R[a][b] = 1;
		else {
			R[a][b] = INF;
			for(int k=1; k<a; k++) push(R[a][b], R[k][b] + R[a-k][b]);
			for(int k=1; k<b; k++) push(R[a][b], R[a][k] + R[a][b-k]);
		}
	}

	for(int a=2; a<=A; a++) for(int b=2; b<=B; b++) 
		for(int c=1; c<a; c++) for(int d=1; d<b; d++) {
			Dy[a][b][c][d] = INF;
			int &dy = Dy[a][b][c][d];
			for(int k=1; k<a-c; k++) push(dy, R[k][b] + Dy[a-k][b][c][d]);
			push(dy, R[a-c][b] + R[c][b-d]);
			for(int k=1; k<c; k++) push(dy, R[k][b-d] + Dy[a-k][b][c-k][d]);

			for(int k=1; k<b-d; k++) push(dy, R[a][k] + Dy[a][b-k][c][d]);
			push(dy, R[a][b-d] + R[a-c][d]);
			for(int k=1; k<d; k++) push(dy, R[a-c][k] + Dy[a][b-k][c][d-k]);
		}
	printf("%d\n", Dy[A][B][C][D]);
	return 0;
}

• Subtask 1: 25 / 25