Official Editorial

Implementation

We can brute force all rotations of the three rectangles with a bitmask of 232^3, with bit ii representing whether the ii'th rectangle should be rotated by 9090 degrees. The rest is just checking if the configurations are valid.

Time Complexity: O(2n⋅side2)\mathcal{O}(2^n \cdot \textbf{side}^2), where nn is the number of rectangles (in this case, 3) and side\textbf{side} as the side length of the square.

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 3;


int main() {
	vector<pair<int, int>> logos(N);
	for (int i = 0; i < N; i++) { scanf("%d%d", &logos[i].first, &logos[i].second); }
	long long area = 0;
	for (pair<int, int> p : logos) { area += p.first * p.second; }

Java

import java.util.*;


public class ThreeLogos {
	private static final int N = 3;


	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int[][] logos = new int[N][2];
		for (int i = 0; i < N; i++) {
			logos[i][0] = scanner.nextInt();

Python

def main():
	import sys


	data = sys.stdin.read().split()


	N = 3
	logos = [(int(data[i * 2]), int(data[i * 2 + 1])) for i in range(N)]


	area = sum(p[0] * p[1] for p in logos)

Alternative Implementation

This problem can be solved in O(1)\mathcal{O}(1) time (ignoring the time to print the output), by simply considering the two possible cases.

If the logos can fit they can either:

  • be placed one under the other, similar to the first sample
  • or one can be placed on top and the other two will be placed next to each other.

C++

#include <bits/stdc++.h>
using namespace std;


struct point {
	int x, y;
	char ch;


	void print(void) {
		for (int i = 0; i < this->y; i++) {
			for (int j = 0; j < this->x; j++) cout << this->ch;

Python

class Logo:
	def __init__(self, x, y, ch):
		# Rotate logos to reduce the amount of casework
		# Longer side = x, shorter side = y
		if x < y:
			y, x = x, y


		self.x = x
		self.y = y
		self.ch = ch

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!

Join Forum