Connection Status:
Competition Arena > Posters

Posters

SRM 157 · 2003-07-28 · by Yarin

SRM 157 · 2003-07-28 · by Yarin · Brute Force, Geometry
Class Name: Posters
Return Type: int
Method Name: maxCover
Arg Types: (int, int, vector<int>, vector<int>)
Problem Statement

Problem Statement

Yarin likes to decorate his walls with posters. Lately, he has had some trouble deciding where on the wall to put the posters so the total area of the wall that is covered with posters is maximized. The posters can of course not be cut into pieces, nor rotated, nor placed so they don't fit completely on the wall. They may overlap however (see example 0).

Create a class Posters containing the method maxCover which takes as input an int width and an int height, the width and height of the wall, and a int[] pWidth and a int[] pHeight, the width and height of each poster. Elements i in pWidth and pHeight are the width and height, respectively, of poster i. The method should return an int, the maximum area of the wall that can be covered with posters.

Constraints

  • width will be between 1 and 100, inclusive.
  • height will be between 1 and 100, inclusive.
  • pWidth will contain between 1 and 5 elements, inclusive.
  • pHeight will contain between 1 and 5 elements, inclusive.
  • pWidth and pHeight will contain the same number of elements.
  • Each element in pWidth will be between 1 and width, inclusive.
  • Each element in pHeight will be between 1 and height, inclusive.
Examples
0)
10
10
{7,4,1,8}
{3,5,3,4}
Returns: 74

The posters can be placed like this: AAAAAAA... AAAAAAABBB AAAAAAABBB ......BBBB ......BBBB ......BBBB DDDDDDDD.. DDDDDDDD.C DDDDDDDD.C DDDDDDDD.C

1)
90
80
{64,51}
{42,51}
Returns: 4964

With only two posters, the optimal result is always reached by putting the posters in opposite corners of the wall.

2)
8
6
{6,6,2,4,2}
{2,2,4,2,4}
Returns: 48

Here one poster must be surrounded by the other posters in order to get the best result.

3)
100
93
{68,50,18,52,62}
{27,15,37,45,50}
Returns: 8256
4)
19
20
{1,2,4,8,16}
{1,2,4,8,16}
Returns: 321

Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Posters with a public method int maxCover(int width, int height, vector<int> pWidth, vector<int> pHeight) · 73 test cases · 2 s / 256 MB per case

Submitting as anonymous