I will describe my thoughts : Let’s say you are at the nth position and you want to find if there exists some choice of indices such that (sum of all a[i]) = (sum of all b[i]) * k for some k. So define F(index, A, B) = true if there exists such choice of indices i <= index such that A = sum of all a[i] and B = sum of b[i] is possible to achieve. Recurrence is fairly simple :

F(index, A, B) = F(index - 1, A, B) | F(index - 1, A - a[i], B - b[i])

The idea is our k will given in the input. And sum of all a[i] and b[i] <= 100*100. So we call F(n, A, B) only for values where A = B * k. And if there exists such choices such that A = sum of those a[i] and B = sum of those b[i], can be achieved then A is a candidate for the maximum answer.

And for the recurrence, at the nth index you have 2 choices, take the nth item or don’t.

But the problem is I will need a dp[100][10000][10000]. Either my approach is completely off the track or it’s possible to improve it. But I don’t understand what the editorial says and also others solutions are not understandable to me. So if anybody can take the trouble to explain your solution, it will be much appreciated.