Min Plus Convolution (Concave and Arbitrary)

2 secs 1024 MB
ecottea's icon ecottea
Tweet
問題
提出
テストケース

問題文

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

Ai+1−Ai≥Ai+2−Ai+1(0≤i≤N−3)A_{i+1} - A_{i} \geq A_{i+2} - A_{i+1} \quad (0 \leq i \leq N-3)

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

Ck=min⁡{Ai+Bj∣i+j=k}(k=0,1,…,N+M−2)C_k = \min \{ A_i + B_j \mid i + j = k \} \quad (k = 0, 1, \ldots, N+M-2)

制約

  • 1≤N,M≤2×1051 \leq N, M \leq 2 \times 10^5
  • ∣Ai∣≤1018(i=0,1,…,N−1)|A_i| \leq 10^{18} \quad (i = 0, 1, \ldots, N-1)
  • ∣Bj∣≤1018(j=0,1,…,M−1)|B_j| \leq 10^{18} \quad (j = 0, 1, \ldots, M-1)
  • 入力はすべて整数

入力

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

NN MM
A0A_0 A1A_1 …\ldots AN−1A_{N-1}
B0B_0 B1B_1 …\ldots BM−1B_{M-1}

出力

長さ N+M−1N+M-1 の整数列 C0,C1,…,CN+M−2C_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)