DMOJ - Phidas

Authors: Jesse Choe, Sofia Yang


Let dp[i][j]\texttt{dp}[i][j] be the minimum total wasted area with a rectangular slab size of i×ji\times j. Initialize dp[i][j]\texttt{dp}[i][j] as iji \cdot j and set dp[xi][yi]\texttt{dp}[x_i][y_i] as 0, where xi,yix_i, y_i are the width and heights of the desired plate sizes, respectively. Check every sub-rectangle with either ii or jj fixed (but not both) and store the minimum total area that must be wasted for the optimal sub-rectangle.

Time Complexity: O(WH(W+H))\mathcal{O}(W\cdot H\cdot (W + H)).

C++

#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

Java

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();

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!