ShoppingSpree
SRM 770 · 2019-10-31 · by jy_25
Problem Statement
You have come to a mall for getting some new clothes. There are n different types of shirts numbered 0, 1, .., n - 1 and m different types of jeans numbered 0, 1, .., m - 1 . For each i from 0 to n - 1 inclusive, a shirt of type i has a value shirtValue i . For each i from 0 to m - 1 inclusive , a jeans of type i has a value jeansValue i . There is an infinite supply of each type of shirts and jeans.
You have got k coupons. There are d deals available numbered 0, 1, .., d - 1. Each deal costs one coupon. For each i from 0 to d - 1 inclusive, the deal numbered i gets you a shirt of type shirtType i and a jeans of type jeansType i . Using some (or all) of your coupons, you want to maximize the sum of values of the distinct shirts and jeans types you get.
Formally, let X be the sum of shirtValue i over all i such that you get atleast one shirt of type i , and Y be the sum of jeansValue i over all i such that you get atleast one jeans of type i . You have to maximize X + Y and return this number
Notes
- A coupon can be used only once.
Constraints
- n, m, k, d will all be between 1 and 100 inclusive.
- shirtValue has exactly n elements.
- jeansValue has exactly m elements.
- shirtType and jeansType have d elements each.
- Every element of shirtType is between 0 and n - 1 inclusive.
- Every element of jeansType is between 0 and m - 1 inclusive.
- Every element of shirtValue is between 1 and 10 6 inclusive.
- Every element of jeansValue is between 1 and 10 6 inclusive
1
{2}
{3}
{0}
{0}
Returns: 5
There's only one deal available, which you purchase with your single coupon. Your shirt is worth 2, and your jeans are worth 3. 2 + 3 = 5.
3
{2, 3, 4}
{3, 2}
{0, 0, 1, 2}
{0, 1, 0, 1}
Returns: 14
If we use deals 0, 2, and 3, we get shirts 0, 1, 2 and jeans 0, 1, so we have at least one of each available shirt and jeans. Thus our total is 14.
1
{2, 3, 4}
{3, 2}
{0, 0, 1, 2}
{0, 1, 0, 1}
Returns: 6
Only one coupon to use, so we can see pretty easily the value of each of the four possible deals to use it on: 5, 4, 6, 6
34
{189382, 613805, 304474, 810883, 479724, 927982, 803943, 931394, 873360, 679491, 601904, 744759, 434840, 445875, 447979, 647111, 916911, 151516, 311978, 408562, 266887, 72183, 720955, 933566, 489774, 739000, 52953, 616093, 61570, 585828, 611488, 451200, 975367, 911915, 51425, 298197, 830668, 418498, 795360, 588091, 639612, 550194, 901682, 711373, 839279, 756996, 217621, 727733, 357592, 63105, 112379, 717731, 216873, 610667, 951301, 66632, 181305, 503073, 370298, 320181, 15969, 188442, 293709, 549395, 284772, 430535, 779447, 38274, 842166, 897845, 604549, 504725, 102139, 954460, 136389, 954749, 927236, 938959, 615489, 978802, 406961, 810919, 352525, 672397, 664257, 973563, 766333, 89457, 761134, 641827, 449352, 366519, 923059, 730045, 152812, 984706, 19817, 225269, 12490, 461138}
{564683, 307704, 146305, 127078, 678339, 199778, 561149, 952323, 630982, 983937, 657136, 230049, 163981, 391991, 548159, 761471, 353621, 866189, 2867, 725438, 922083, 296953, 132847, 28499, 540013, 376735, 1035, 721922, 616976, 477187, 741264, 994237, 850898, 793386, 761397, 371363, 956024, 813604, 7871, 81179, 375320, 270110, 722652, 656663, 146350, 722756, 657256, 309377, 932049, 577724, 705965, 135650, 220962, 160678, 370077, 605981, 458140, 127670, 903777, 940260, 983551, 264328, 677521, 3946, 16073, 411767, 125197, 317250, 750002, 344352, 873667, 876747, 925570, 762883, 780975, 684687, 947256, 646918, 111973, 354149, 743556, 823271, 307875, 989703, 938191, 670211, 540505, 77350, 911408, 384098, 250773, 337014, 708006, 203563, 188592, 346922, 168504, 307273, 213950, 833359}
{73, 34, 99, 92, 73, 27, 72, 99, 43, 53, 14, 57, 87, 69, 36, 92, 29, 10, 67, 62, 95, 32, 37, 17, 16, 82, 68, 15, 42, 73, 74, 64, 79, 58, 29, 93, 63, 65, 78, 13, 4}
{44, 1, 59, 97, 36, 88, 74, 46, 11, 31, 89, 68, 12, 38, 0, 15, 88, 38, 9, 47, 72, 75, 42, 7, 12, 7, 20, 52, 52, 75, 69, 48, 19, 38, 79, 72, 31, 91, 14, 20, 25}
Returns: 37080301
37
{629683, 577221, 565659, 356300, 639097, 206243, 909632, 799394, 519483, 677301, 374883, 624520, 633921, 902456, 290171, 821843, 856338, 851137, 930754, 95671, 644968, 202437, 588842, 64061, 369577, 750450, 123149, 784642, 312351, 337500, 512761, 663850, 452721, 353469, 614170, 89421, 382911, 17027, 649722}
{179498, 247735, 594079, 270467, 850735, 108970, 107855, 647391, 578519, 796516, 254142, 896185, 39170, 379667, 707514, 575598, 92387, 940588, 826030, 211811, 176199, 988242, 679844, 645695, 810312, 948624, 74731, 251730, 267336, 83568, 104475, 486564, 493628, 547002, 32938, 482304, 867478, 973169, 993809, 476186, 908804, 702250, 13847, 762656, 580091, 695783, 440971, 924527, 839700, 895572, 81468, 657157, 178652, 29191, 638494, 998902, 76343, 658307, 242003, 763714, 408139, 186684, 161429, 632456, 428844, 109192, 870872, 288032, 775903, 587471, 105814, 714516, 945707, 500793, 392760, 117426, 957499, 370645, 582089, 961676, 283163, 580432, 760435, 197178, 599067, 902323, 464167, 589399, 952923, 190355, 212804, 723614, 703921, 906475, 732855, 6257, 794713, 2674, 82769, 365518}
{23, 34, 22, 7, 23, 12, 12, 11, 15, 23, 15, 12, 11, 13, 18, 9, 8, 15, 37, 35, 14, 6, 20, 33, 3, 27, 6, 22, 2, 22, 11, 3, 10, 16, 18, 0, 26, 16, 21, 26, 3, 2, 10, 15, 19, 13, 24, 16, 37, 13, 19, 32, 11, 37, 5, 20, 38, 14, 17, 36, 37, 33, 11, 8, 17, 9, 18, 38, 2, 0, 30, 17, 4, 17, 7, 35, 23, 18, 9, 31, 33, 35}
{53, 50, 60, 66, 5, 71, 82, 83, 45, 24, 68, 5, 35, 97, 37, 88, 49, 93, 78, 95, 50, 36, 33, 23, 2, 7, 17, 30, 4, 53, 50, 73, 2, 20, 64, 69, 98, 10, 76, 86, 50, 2, 91, 60, 87, 64, 42, 48, 90, 11, 13, 18, 16, 66, 63, 73, 25, 14, 4, 76, 32, 79, 32, 15, 44, 89, 68, 20, 53, 38, 92, 9, 35, 60, 29, 24, 8, 65, 36, 16, 13, 24}
Returns: 44247456
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ShoppingSpree with a public method int maxValue(int k, vector<int> shirtValue, vector<int> jeansValue, vector<int> shirtType, vector<int> jeansType) · 69 test cases · 2 s / 256 MB per case