Min Plus Convolution (Concave and Arbitrary)

2 secs 1024 MB
ecottea's icon ecottea

問題文

長さ NN の整数列 A0,A1,,AN1A_0, A_1, \ldots, A_{N-1} と長さ MM の整数列 B0,B1,,BM1B_0, B_1, \ldots, B_{M-1} が与えられます.ここで A0,A1,,AN1A_0, A_1, \ldots, A_{N-1} は上に凸です.すなわち

Ai+1AiAi+2Ai+1(0iN3)A_{i+1} - A_{i} \geq A_{i+2} - A_{i+1} \quad (0 \leq i \leq N-3)

をみたします.以下の式で定まる長さ N+M1N+M-1 の整数列 C0,C1,,CN+M2C_0, C_1, \ldots, C_{N+M-2} を求めてください.

Ck=min{Ai+Bji+j=k}(k=0,1,,N+M2)C_k = \min \{ A_i + B_j \mid i + j = k \} \quad (k = 0, 1, \ldots, N+M-2)

制約

  • 1N,M2×1051 \leq N, M \leq 2 \times 10^5
  • Ai1018(i=0,1,,N1)|A_i| \leq 10^{18} \quad (i = 0, 1, \ldots, N-1)
  • Bj1018(j=0,1,,M1)|B_j| \leq 10^{18} \quad (j = 0, 1, \ldots, M-1)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます.

NN MM
A0A_0 A1A_1 \ldots AN1A_{N-1}
B0B_0 B1B_1 \ldots BM1B_{M-1}

出力

長さ N+M1N+M-1 の整数列 C0,C1,,CN+M2C_0, C_1, \ldots, C_{N+M-2} を半角空白区切りで一行に出力してください.

最後に改行してください.

サンプル

入力1
8 9
-1 4 6 7 7 5 3 -2
3 1 4 1 5 9 2 6 5
出力1
2 0 3 0 4 7 1 1 -1 2 -1 3 5 0 4 3 

例えば

C2=min{A0+B2,A1+B1,A2+B0}=min{3,5,9}=3C_2 = \min \{ A_0 + B_2, A_1 + B_1, A_2 + B_0 \} = \min \{ 3, 5, 9 \} = 3

などとなります.

提出


Go (1.21)