이차 정수 계획 문제

이 문제는 잘 알려진 NP 문제인 이차 정수 계획 문제를 푸는 것이다.

이차 정수 계획 문제에는 변수가 있다. 아래 조건을 모두 만족하는 길이 $n$의 정수 수열 $(x_1, x_2, \ldots, x_n)$을 구해야 한다.

이차 정수 계획 문제에는 제약 조건도 있다. 주어진 수열은 다음 두 종류의 제약 조건을 모두 만족해야 한다.

1. 양의 정수 $k$ ($3 \le k \le 5$)와 $n$개의 구간 $[l_i, r_i]$ ($1 \le i \le n$)가 주어진다. 이때 $1 \le l_i \le r_i \le k$이다. 모든 $1 \le i \le n$에 대해 $l_i \le x_i \le r_i$를 만족해야 한다.
2. $m$개의 세 쌍 $(p_j, q_j, b_j)$가 주어진다. 모든 $1 \le j \le m$에 대해 $|x_{p_j} - x_{q_j}| \le b_j$를 만족해야 한다.

목적 함수도 있다. 가중치 $v_2, v_3, \ldots, v_{k-1}$ ($k-2$개)이 주어진다. $c_i$는 수열에서 값이 $i$인 원소의 개수이다. $G$는 $|x_i - x_j| \le 1$을 만족하는 순서쌍 $(i, j)$의 개수이며, $1 \le i, j \le n$이다. $i \ne j$이면 $(i, j)$와 $(j, i)$는 서로 다른 쌍으로 센다. 수열 $x_1, x_2, \ldots, x_n$의 가중치는 다음과 같다.

$W(x_1, x_2, \ldots, x_n) = 10^{6} G + \sum_{i = 2}^{k - 1} c_i v_i$

제약 조건을 만족하는 수열 가운데 가중치가 최대인 것을 찾아야 한다.

이차 정수 계획 문제에서 질의가 여러 번 필요한 것은 아니지만, 이 문제에서는 $q$개의 질의가 주어진다. 각 질의마다 가중치 $v_2, v_3, \ldots, v_{k-1}$이 다르게 주어지며, 그때마다 제약을 만족하는 최대 가중치 수열을 찾아야 한다. 출력을 줄이기 위해 그 수열의 가중치만 출력하면 된다. 데이터에는 조건을 만족하는 수열이 적어도 하나 존재함이 보장된다.

여러 개의 테스트 데이터가 주어진다. 첫 줄에는 테스트 케이스 번호 $C$와 데이터 세트의 개수 $T$가 주어진다. $C = 0$이면 해당 데이터 세트는 예제이다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫 줄에 정수 $k, n, m, q$가 주어진다. 각각 수열의 값 범위, 수열의 길이, 변수 사이 제약의 개수, 질의의 개수이다.
• 다음 $n$개 줄에 정수 $l_i$, $r_i$가 주어진다. $i$번째 원소의 값 범위이다.
• 다음 $m$개 줄에 정수 $p_j$, $q_j$, $b_j$가 주어진다. 한 쌍의 변수에 대한 제약이다.
• 다음 $q$개 줄에 각각 $k-2$개의 음이 아닌 정수 $v_2, v_3, \ldots, v_{k-1}$이 주어진다. 한 질의의 가중치 매개변수이다.

각 데이터 세트의 각 질의마다 최대 가중치를 한 줄에 출력한다.

$\sum q$는 한 테스트 포인트 안에 있는 모든 데이터 세트의 $q$를 합한 값이다. 모든 테스트 포인트에 대해 다음이 성립한다.

• $1 \le T \le 600$
• $i$번째 ($1 \le i \le T$) 테스트 데이터에서 $1 \le n \le \max(T/i, 2 \log_2 T)$
• $3 \le k \le 5$, $0 \le m \le 3n$, $1 \le q$, $\sum q \le 3 \times 10^5$
• $1 \le l_i \le r_i \le k$
• $1 \le p_j, q_j \le n$, $0 \le b_j < k$
• $0 \le v_2, \ldots, v_{k-1} \le 10^{12}$

• 특수 조건 A: $m = 0$이다.
• 특수 조건 B: $m \le 10$이고, 한 테스트 포인트의 모든 데이터 세트에 걸친 $m$의 합은 $200$을 넘지 않는다.
• 특수 조건 C: 데이터는 무작위로 생성된다. 각 데이터 세트마다 먼저 매개변수 $k, n, m, q$와 $p_{k-1} \ne 0$인 음이 아닌 정수 $p_0, p_1, \ldots, p_{k-1}$을 정한다. 그다음 다음 규칙으로 데이터를 만든다.
  • 각 $1 \le i \le n$에 대해 $x, y \in [1, k]$를 독립적으로 균등하게 뽑는다. $l_i = \min(x, y)$, $r_i = \max(x, y)$로 둔다.
  • 세 쌍이 $m$개가 될 때까지 다음을 반복한다.
    • $u, v \in [1, n]$을 독립적으로 균등하게 뽑는다.
    • $p$를 가중치로 하여 $w$를 뽑는다. $0 \le i \le k-1$에 대해 $w = i$일 확률은 $\frac{p_i}{p_0 + p_1 + \cdots + p_{k-1}}$이다.
    • $(u, v, w)$를 추가하면 유효한 수열이 없어지면 이 세 쌍을 버린다. 그렇지 않으면 추가한다.
  • 각 질의의 $v_2, \ldots, v_{k-1}$은 $[0, 10^{12}]$에서 독립적으로 균등하게 뽑는다.