Connection Status:
Competition Arena > EqualTowers

EqualTowers

SRM 442 · 2009-06-13 · by mateuszek

SRM 442 · 2009-06-13 · by mateuszek · Dynamic Programming
Class Name: EqualTowers
Return Type: int
Method Name: height
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Johnny has some number of rectangular bricks. He can put bricks on top of each other to build a tower. He wishes to build two towers of equal height out of his bricks (each tower must contain at least one brick). He also wants the towers to be as tall as possible. Note that Johnny doesn't have to use all the bricks.

You are given a int[] bricks, where each element is the height of a single brick. Return the height of the tallest towers of equal height that Johnny can build. If it's impossible to build two towers of equal height, return -1 instead.

Constraints

  • bricks will contain between 1 and 50 elements, inclusive.
  • Each element of bricks will be between 1 and 500000, inclusive.
  • The sum of all elements of bricks will not be greater than 500000.
Examples
0)
{ 2, 3, 5 }
Returns: 5

Johnny can build two towers of height 5. One contains a single brick of height 5, and the other contains a brick of height 2 and a brick of height 3.

1)
{ 10, 9, 2 }
Returns: -1

There's nothing Johnny can do here.

2)
{ 11, 11 }
Returns: 11
3)
{ 88242, 313, 1991, 4207, 2483, 1763, 224, 16, 582, 22943, 28632, 47682, 378, 90, 88, 43, 117, 19, 8 }
Returns: 99901
4)
{ 188242, 313, 1991, 4207, 2483, 1763, 224, 16, 582, 22943, 111653, 23787, 16820, 12415, 1270, 3032, 2293, 5221, 396, 42 }
Returns: 199661

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

Coding Area

Language: C++17 · define a public class EqualTowers with a public method int height(vector<int> bricks) · 91 test cases · 2 s / 256 MB per case

Submitting as anonymous