oj.uz

Submission #26005

# Submission time Handle Problem Language Result Execution time Memory
26005 2017-06-26T06:06:15 Z kajebiii L 모양의 종이 자르기 (KOI15_cut) C++14
25 / 25
 443 ms 37776 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 37776 KB Output is correct
2 Correct 89 ms 37776 KB Output is correct
3 Correct 436 ms 37776 KB Output is correct
4 Correct 243 ms 37776 KB Output is correct
5 Correct 386 ms 37776 KB Output is correct
6 Correct 0 ms 37776 KB Output is correct
7 Correct 0 ms 37776 KB Output is correct
8 Correct 0 ms 37776 KB Output is correct
9 Correct 0 ms 37776 KB Output is correct
10 Correct 0 ms 37776 KB Output is correct
11 Correct 419 ms 37776 KB Output is correct
12 Correct 0 ms 37776 KB Output is correct
13 Correct 6 ms 37776 KB Output is correct
14 Correct 99 ms 37776 KB Output is correct
15 Correct 36 ms 37776 KB Output is correct
16 Correct 336 ms 37776 KB Output is correct
17 Correct 303 ms 37776 KB Output is correct
18 Correct 136 ms 37776 KB Output is correct
19 Correct 33 ms 37776 KB Output is correct
20 Correct 443 ms 37776 KB Output is correct