I want to apologize for the problem D. There was a bug in model solution. Moreover, this problem may not be solvable in polynomial time even with such constraints on the number's size. We will investigate it. I hope nobody will feel offended in any case.
UPD: Now I am pretty sure that my model solution for the problem D was completely wrong. I want to apologize for it again. There will be no rejudge of the solutions accepted during the contest. The statement will be changed so that it will ask to find the LCIS of the two sequences. This problem definitely has a solution.
UPD: Problem D was changed as I promised.