ShoppingSpree | Topcoder Archive

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

Definition

Class:: ShoppingSpree
Method:: maxValue
Parameters:: int, int[], int[], int[], int[]
Returns:: int
Method signature:: int maxValue(int k, int[] shirtValue, int[] jeansValue, int[] shirtType, int[] jeansType)
(be sure your method is public)

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

Examples

```
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

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.