## Editorial for Mock CCC '19 Contest 1 J5 - Pusheen Designs a Sushi Boat

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

For the first subtask, the answer is always .

For the second subtask, there is an solution that consists of looping over all pairs of pieces of sashimi and counts the number of pairs which come from distinct fish.

To get full credit, the above solution cannot be directly generalized as that would run in . We instead need to be more careful in how we enumerate these options.

Imagine that we loop over the fish in order from to , and at each point in time we decide whether to select one piece of sashimi from that fish or not. If we take this approach, then the only meaningful component of our state is how many pieces of sashimi we have taken.

Define to be the number of ways to select pieces of sashimi using only pieces from the first fish. We have that and where we define to be the number of pieces of sashimi from fish that we can select.

With memoization, this DP takes space and runs in time.

## Comments