Editorial for DMOPC '18 Contest 4 P2 - Dr. Henri and Responsibility
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
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 .