## Editorial for DMOPC '18 Contest 4 P2 - Dr. Henri and Responsibility

Remember to use this editorial

**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.**Authors:

For of points, we can consider each possible partitioning scheme. There are such partitions to consider, and it takes time to find the difference between the sum of the two partitions.

**Time Complexity:**

For the remaining of points, we can solve this problem with dynamic programming. We let be true if there exists a subset of the first tasks that sums to . We obtain the recurrence If we directly implement this, saving the result to each visited state, our array will be too big. However, we see that for each , is dependent on only . Thus we save only the previous row, for a memory complexity of .

**Time Complexity:**

## Comments