BrightLamps
TCO14 Round 3A · 2014-03-26 · by rng_58
TCO14 Round 3A · 2014-03-26 · by rng_58 · Math
Problem Statement
Problem Statement
N lamps are arranged in a line. The lamps are numbered 0 through N-1 from left to right.
You are given aString init describing the initial state of the lamps. If the i-th (0-based) character of init is '1', the lamp i is initially turned on. If the i-th character of init is '0', the lamp i is initially turned off. You are also given a int[] a. When the lamp i is turned on, the brightness of the lamp is a[i]. When the lamp i is turned off, the brightness of the lamp is zero.
Toastman wants to maximize the total brightness of these lamps. He is allowed to toggle the states of some lamps according to the following rules: In each step, he can choose K consecutive lamps and toggle all their states. Return the largest possible total brightness Toastman can produce by making zero or more consecutive steps.
You are given a
Toastman wants to maximize the total brightness of these lamps. He is allowed to toggle the states of some lamps according to the following rules: In each step, he can choose K consecutive lamps and toggle all their states. Return the largest possible total brightness Toastman can produce by making zero or more consecutive steps.
Constraints
- init will contain between 1 and 2500 characters, inclusive.
- Each character in init will be either '0' or '1'.
- The number of elements in a will be the same as the number of characters in init.
- Each element of a will be between 1 and 1000, inclusive.
- K will be between 1 and the number of characters in init, inclusive.
Examples
0)
"011"
{3, 2, 4}
2
Returns: 7
The optimal solution is to toggle the states of the first two lamps. The total brightness will then be 3+0+4 = 7.
1)
"0010100101"
{1, 1, 1, 3, 4, 3, 4, 5, 1, 5}
1
Returns: 28
Here you can turn on all lamps.
2)
"1111111111"
{5, 5, 3, 3, 4, 3, 5, 1, 1, 3}
7
Returns: 33
You are allowed not to perform any operations.
3)
"0010000001"
{8, 3, 10, 8, 3, 7, 4, 6, 3, 10}
4
Returns: 55
In each optimal solution of this test case some lamps have to be toggled multiple times.
4)
"00001001010101100001100000010000011001000000001011"
{99, 29, 22, 50, 17, 49, 50, 54, 43, 29, 30, 33, 38, 53, 71, 48, 82, 25, 62, 93, 90, 64, 43, 95, 68,
35, 79, 11, 13, 47, 51, 44, 35, 55, 4, 34, 7, 10, 25, 38, 29, 58, 36, 34, 77, 90, 37, 58, 20, 20}
17
Returns: 2068
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BrightLamps with a public method int maxBrightness(string init, vector<int> a, int K) · 72 test cases · 2 s / 256 MB per case