独自の動的計画法の問題。

Genre: combinatorial optimization, dynamic programming.
This is a canonical "minmax" optimization problem in which the objective is to minimize the maximal difference between the sum of max times for one team and the min times for another (disjoint) team. The dynamic programming algorithm I originally attempted was a greedy approach, attempting to move over the pet producing the minimal max difference in each step. This code ran in O(n^3) and provided correct output for several smaller (5 or fewer elements) test cases. However, this was apparently not a globally optimal solution as, for a 6 element test case, the solution was greater than the test engine's optimal solution. The case was:
{2907,949,1674,6092,8608,5186} {7296,6954,4407,9724,8645,8065}
and the optimal placement into T was the set of indices {2,3,5}, but my algorithm outputted {3,4} using the greedy strategy.
The editorial site discusses a different dynamic programming approach based on the (s,t) pair. Here t is the index of the greatest element for which no team S->T move decision has been made, while s is the sum of the A and B values for all members of T. This is because the problem is reduced to finding, for any assignment to T, the max of B(T)-A(S) and B(S)-A(T). Then the min is taken over all T values. But B(T)-A(S) = B(T)-tA+A(T) and B(S)-A(T) = tB-B(T)-A(T), where tA is the total time for A and tB is the total time for B. Thus, if A(T)+B(T)=s is known, then the two quantities to be compared by the max function are known (as tA and tB, the sums of all elements in A and B vectors, are constant). The key insight to this problem is that the "max diff" quantity to be minimized can be determined uniquely given the s sum above. s is determined by the allocation between teams, but, for each t, all s values can be searched. Only the s values that are reachable from (t=n,s=0) will factor into the solution, though. The complexity is thus O(50*10^6), as there are 50 possible t values (in maximal A, B case) and at most (50*2*10000) s values (as A[i], B[i]<=10000).
The key insight is that a recursion can be defined by selecting t index values in decreasing order, and this recursion enables the solution space to be traversed by increasing both t and s. Given that all members from index t on have been placed, and that the current s=A(T)+B(T) is set, the problem is to find the minimum placement of members 0...t-1, defined by the difference function f(t,s). If the tth member is moved, s increases by A[t]+B[t], and f(t,s)=f(t-1,s+A[t]+B[t]). Otherwise, f(t,s)=f(t-1,s). Thus f(t,s)=min(f(t-1,s),f(t-1,s+A[t]+B[t])). However, looking at this recursion we can iterate over t in increasing order, as only f(t-1,...) values are needed (as long as f(t-1,s') is known for all s' values). This is possible even though the recursion definition implies a knowledge of the later placements of indices above t, as this is what the s value encodes. The base case, when all T placements have been determined, for any f(0,s) value, is max(s-tA,tB-s). Thus the O(NM) = 50*10^6 complexity.