ChristmasPudding
SRM 773 · 2019-12-20 · by misof
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) < 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 )
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.
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}
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 ChristmasPudding with a public method long long eat(int N, long long Vall, long long Vsweet, vector<int> Vprefix, vector<int> Tprefix, vector<int> Sprefix, int seed) · 78 test cases · 2 s / 256 MB per case