BuildingTowers
SRM 647 · 2014-12-30 · by lg5293
Problem Statement
The citizens of Byteland want to build N new buildings.
The new buildings will all stand in a line and they will be labeled 1 through N, in order.
The city regulations impose some restrictions on the heights of the new buildings.
You are given the parameters used in these restrictions: an
- The height of each building must be a nonnegative integer.
- The height of building 1 must be 0.
- The absolute value of the difference between any two adjacent buildings must be at most K.
- For each valid i, the height of building x[i] must be t[i] or less.
Given these restrictions, the citizens of Byteland want to build a building that will be as tall as possible. Return the largest possible height some of the N buildings may have.
Constraints
- N will be between 1 and 1,000,000,000, inclusive.
- K will be between 1 and 1,000,000,000, inclusive.
- x will contain between 0 and min(N,500) elements, inclusive.
- t will have exactly the same number of elements as x
- Each element of x will be between 1 and N, inclusive.
- x[i] < x[i+1] for all valid i.
- Each element of t will be between 1 and 1,000,000,000, inclusive.
10
1
{3,8}
{1,1}
Returns: 3
In this case we are going to build 10 buildings. The difference in height between adjacent buildings is at most 1. We also have two additional constraints: the height of building 3 can be at most 1, and the height of building 8 can also be at most 1. The tallest possible new building in this city can have height 3. One optimal skyline looks as follows: {0,1,1,2,3,3,2,1,1,0}.
1000000000
1000000000
{}
{}
Returns: 999999999000000000
There are no additional constraints so, for each valid i, the height of building i can be (i-1)*1000000000.
20
3
{4,7,13,15,18}
{8,22,1,55,42}
Returns: 22
780
547990606
{34,35,48,86,110,170,275,288,313,321,344,373,390,410,412,441,499,525,538,568,585,627,630,671,692,699,719,752,755,764,772}
{89,81,88,42,55,92,19,91,71,42,72,18,86,89,88,75,29,98,63,74,45,11,68,34,94,20,69,33,50,69,54}
Returns: 28495511604
7824078
2374
{134668,488112,558756,590300,787884,868112,1550116,1681439,1790994,
1796091,1906637,2005485,2152813,2171716,2255697,2332732,2516853,
2749024,2922558,2930163,3568190,3882735,4264888,5080550,5167938,
5249191,5574341,5866912,5936121,6142348,6164177,6176113,6434368,
6552905,6588059,6628843,6744163,6760794,6982172,7080464,7175493,
7249044}
{8,9,171315129,52304509,1090062,476157338,245,6,253638067,37,500,
29060,106246500,129,22402,939993108,7375,2365707,40098,10200444,
3193547,55597,24920935,905027,1374,12396141,525886,41,33,3692,
11502,180,3186,5560,778988,42449532,269666,10982579,48,3994,1,9}
Returns: 1365130725
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BuildingTowers with a public method long long maxHeight(int N, int K, vector<int> x, vector<int> t) · 78 test cases · 2 s / 256 MB per case