Phidias

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
 
#define f first
#define s second
 
const int MAXN = 600;
 
/*
 * Sea dp[i][j] el área residual mínima con una
 * losa rectangular de tamaño i x j
 */
int dp[MAXN + 1][MAXN + 1];
 
int main() {
	// El ancho y la altura de la losa original.
	int w, h;
	cin >> w >> h;
	int n;
	cin >> n;
	vector<pi> plates(n);
	for (int i = 0; i < n; i++) {
		// El ancho y la altura de las placas deseadas
		cin >> plates[i].f >> plates[i].s;
	}
	for (int i = 1; i <= w; i++) {
		for (int j = 1; j <= h; j++) {
			dp[i][j] = i * j;  // Inicializar dp[i][j] como i * j
		}
	}
	for (int i = 0; i < n; i++) {
		/*
		 * Poner dp[x_i][y_i] en 0, donde x_i e y_i son el ancho
		 * y la altura de los tamaños de placa deseados, respectivamente.
		 */
		dp[plates[i].f][plates[i].s] = 0;
	}
	/*
	 * Visitar todos los rectángulos posibles con un ancho de
	 * i = 1...w y una altura de j = 1...h
	 */
	for (int i = 1; i <= w; i++) {
		for (int j = 1; j <= h; j++) {
			for (int x = 1; x <= i; x++) {
				/*
				 * Fijar la altura del rectángulo y hallar el
				 * subrectángulo óptimo con altura j
				 */
				dp[i][j] = min(dp[i][j], dp[x][j] + dp[i - x][j]);
			}
			for (int y = 1; y <= j; y++) {
				/*
				 * Fijar el ancho del rectángulo y hallar el
				 * subrectángulo óptimo con ancho i
				 */
				dp[i][j] = min(dp[i][j], dp[i][y] + dp[i][j - y]);
			}
		}
	}
	cout << dp[w][h] << endl;
}

import java.io.*;
import java.util.*;
 
public class Phidias {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int W = io.nextInt();
		int H = io.nextInt();
		int N = io.nextInt();
 
		// DP[i][j] es el espacio mínimo desperdiciado dada una i * j rectángulo.
		int[][] dp = new int[W + 1][H + 1];
 
		// Por defecto, todo el espacio de la losa se desperdicia.
		for (int i = 0; i <= W; i++) {
			for (int j = 0; j <= H; j++) { dp[i][j] = i * j; }
		}
 
		// Se desperdicia 0 espacio si la losa tiene el mismo tamaño que las placas.
		for (int i = 0; i < N; i++) {
			int x = io.nextInt();
			int y = io.nextInt();
			dp[x][y] = 0;
		}
 
		/*
		 * Recorrer todas las losas posibles
		 * con ancho de 1 a w y altura de 1 a h.
		 */
		for (int i = 1; i <= W; i++) {
			for (int j = 1; j <= H; j++) {
				for (int a = 1; a <= i; a++) {
					// Fijar el corte vertical para calcular el área mínima
					// desperdiciada.
					dp[i][j] = Math.min(dp[i][j], dp[a][j] + dp[i - a][j]);
				}
				for (int b = 1; b <= j; b++) {
					// Fijar el corte horizontal para calcular el área mínima
					// desperdiciada.
					dp[i][j] = Math.min(dp[i][j], dp[i][b] + dp[i][j - b]);
				}
			}
		}
		System.out.println(dp[W][H]);
	}
 
	// CodeSnip{Kattio}
}