P3308 [SDOI2014] LIS

Given a sequence $A$, each element $A_i$ has a deletion cost $B_i$ and an additional attribute $C_i$. Delete some elements so that the length of the longest increasing subsequence of $A$ decreases by at least $1$, while minimizing the sum of deletion costs, and output the solution. If there are multiple solutions, output the one whose deleted elements’ additional attributes, after sorting, form the lexicographically smallest sequence.

The input contains multiple test cases. The first line contains an integer $T$, the number of test cases. The next $4T$ lines describe the test cases. For each test case, the first line contains an integer $N$, the number of elements in $A$. The next three lines each contain $N$ integers: $A_1\sim A_n$, $B_1\sim B_n$, $C_1\sim C_n$, satisfying $1\le A_i,B_i,C_i \le 10^9$, and all $C_i$ are pairwise distinct.

For each test case, output two lines. The first line contains two integers $S, M$, denoting the total deletion cost and the number of deleted elements, respectively. The second line contains $M$ integers, the positions in $A$ of the deleted elements, in increasing order.

[Sample explanation] Deleting $(A_2,A_3,A_6)$, $(A_1,A_6)$, $(A_2,A_3,A_4,A_5)$, etc., are all valid solutions, but $(A_2,A_3,A_6)$ yields the lexicographically smallest sequence of $C$ values. For $100\%$ of the testdata, $1\le N\le 700$, $1\le T\le 5$. Translated by ChatGPT 5