ChristmasPudding | Topcoder Archive

Problem Statement

You have probably heard the phrase "the proof is in the pudding". And if you did hear it, you probably thought that it is nonsense. And if you did think that, you were right. It is nonsense, because this is a distorted version of the original saying: "the proof of the pudding is in the eating". The meaning of this phrase is that you should not judge the quality of something before you experience it.

In this problem, we are going to do just that: eat some pudding.

There are N different puddings available. Some are sweet, some are savory. You have three goals:

You want to eat exactly Vall spoons of pudding. If you cannot do that, you will simply eat all the available pudding.
You want to eat at least Vsweet spoons of sweet pudding. If you cannot do that, you will simply eat all the available sweet pudding.
Given the previous two goals, you want to maximize your happiness (as explained below).

The puddings are numbered 0 to N-1. The volume of pudding i is V[i] spoons. The tastiness of pudding i is T[i]. The value S[i] is 1 if the pudding is sweet and 0 if it's savory.

You are allowed to eat as much of each pudding as you like (possibly leaving parts of multiple puddings uneaten). Each spoonful of the pudding increases your happiness by its tastiness. Compute and return the maximum happiness you can obtain by eating the puddings.

Use the pseudocode below to generate the arrays V, T, and S.

V, T, S = Vprefix, Tprefix, Sprefix
state = seed
while length(V) &lt; N:
    state = (state * 1103515245 + 12345) modulo 2^31
    V.append( 1 + (state modulo 10^6) )
    state = (state * 1103515245 + 12345) modulo 2^31
    T.append( 1 + (state modulo 10^6) )
    state = (state * 1103515245 + 12345) modulo 2^31
    S.append( (state div 1024) modulo 2 )

Definition

Class:: ChristmasPudding
Method:: eat
Parameters:: int, long, long, int[], int[], int[], int
Returns:: long
Method signature:: long eat(int N, long Vall, long Vsweet, int[] Vprefix, int[] Tprefix, int[] Sprefix, int seed)
(be sure your method is public)

Notes

Watch out for integer overflows. In particular, we recommend using 64-bit integers when generating the arrays V, T, and S.
The reference solution does not depend on any properties of the pseudorandom generator. It would correctly solve each input that matches the constraints.

Constraints

N will be between 1 and 200,000, inclusive.
0 <= Vsweet <= Vall <= 10^12.
Vprefix, Tprefix and Sprefix will have the same number of elements.
The number of elements in Vprefix will be between 0 and min(100,N), inclusive.
Each element of Vprefix will be between 1 and 1,000,000, inclusive.
Each element of Tprefix will be between 1 and 1,000,000, inclusive.
Each element of Sprefix will be 0 or 1.
seed will be between 0 and 2^31 - 1, inclusive.

Examples

```
3
```
```
300
```
```
220
```
```
{100, 100, 200}
```
```
{4, 5, 7}
```
```
{1, 0, 1}
```
```
47
```
```
Returns: 1880
```
There are three puddings: 100 spoons of sweet pudding with tastiness 4, 100 spoons of savory pudding with tastiness 5, and 200 spoons of sweet pudding with tastiness 7. We want to eat exactly 300 spoons of pudding, out of which at least 220 should be sweet. The optimal solution is to eat 20 spoons of pudding #0, 80 spoons of pudding #1, and 200 spoons of pudding #2. The total happiness we'll gain will be 20*4 + 80*5 + 200*7 = 1880.
```
3
```
```
390
```
```
220
```
```
{100, 100, 200}
```
```
{4, 5, 7}
```
```
{1, 0, 1}
```
```
4747
```
```
Returns: 2260
```
The same setting as in Example #0, but now we want to eat a total of 390 spoons of pudding. The optimal solution is to eat 90 spoons of pudding #0, the whole pudding #1, and the whole pudding #2.
```
3
```
```
300
```
```
300
```
```
{100, 200, 300}
```
```
{30, 10, 20}
```
```
{0, 1, 0}
```
```
42
```
```
Returns: 5000
```
We would like to eat exactly 300 spoons of pudding. That can be done. We would also like to eat at least 300 spoons of sweet pudding. That cannot be done, as there are only 200 spoons of sweet pudding. Hence, we will eat all those 200 spoons of sweet pudding (to satisfy our second goal) and also 100 spoons of savory pudding (to satisfy the first goal). The optimal solution is to eat the whole pudding #0 and the whole pudding #1, leaving pudding #2 untouched.
```
2
```
```
100
```
```
0
```
```
{47, 10}
```
```
{3, 5}
```
```
{0, 0}
```
```
5
```
```
Returns: 191
```
We want to eat 100 spoons of pudding, but there are only 47 + 10 = 57 spoons of pudding. Thus, we simply eat all the pudding.
```
20
```
```
5000000
```
```
3000000
```
```
{470}
```
```
{407}
```
```
{0}
```
```
4747
```
```
Returns: 3528114042726
```
Use this example to check whether you are generating the input correctly. You should get the following arrays: V = {470, 262889, 589672, 702899, 546746, 927533, 688636, 441879, 104622, 107313, 754256, 815739, 562274, 293045, 533348, 205407, 310614, 187897, 415160, 748227} T = {407, 911298, 378453, 456644, 573439, 754742, 840985, 980824, 401891, 183530, 590749, 234988, 167431, 118622, 322465, 359744, 581611, 868882, 360165, 944980} S = {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0}
```
10
```
```
0
```
```
0
```
```
{}
```
```
{}
```
```
{}
```
```
0
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.