F - 集合 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 4 点

問題文

(1, 2, \dots, N) の順列 P = (P_1, P_2, \dots, P_N) および長さ N の整数列 A_1, A_2, \dots, A_N が与えられます。

整数集合 \lbrace 1,2,\dots, N \rbrace の部分集合 S であって以下の条件を満たすものを 良い集合 と呼びます。

  • x \lt y かつ x, y \in S である整数の組 (x, y) 全てに対して以下の条件が成り立つ。
    • z を P_z = \min(P_x, P_{x+1}, \dots, P_y) を満たす整数とする。(このような z は一意に定まる。) この時、z \in S が成り立つ。

良い集合 S の コスト を \displaystyle \sum_{i \in S} A_i として定義します。
K = 1, 2, \dots, N について、サイズ K の良い集合のコストとしてあり得る値の最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 5000
  • 1 \leq N \leq 5000
  • 1 \leq A_i \leq 10^9
  • (P_1, P_2, \dots, P_N) は (1,2,\dots,N) の順列
  • 全てのテストケースに対する N の総和は 5000 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N
P_1 P_2 \dots P_N
A_1 A_2 \dots A_N

出力

T 行出力せよ。i 行目には i 番目のテストケースの答えを出力せよ。
各テストケースでは、K=1,2,\dots,N に対する答えを空白区切りで 1 行に出力せよ。

入力例 1

3
4
4 1 2 3
1 8 2 4
6
5 3 2 4 6 1
73 38 30 85 27 45
10
4 10 3 7 2 6 8 9 5 1
853822501 687675302 281611653 844033520 423210108 339630584 780395612 207907746 285523486 359061085

出力例 1

1 6 11 15
27 57 95 140 213 298
207907746 493431232 833061816 1192122901 1537883577 1896944662 2584619964 3365015576 4209049096 5062871597

1 番目のテストケースでは、

  • K=1 の時は S=\lbrace 1 \rbrace が、
  • K=2 の時は S=\lbrace 3,4 \rbrace が、
  • K=3 の時は S=\lbrace 1,2,3 \rbrace が、
  • K=4 の時は S=\lbrace 1,2,3,4 \rbrace が良い集合の中でコスト最小です。

Score : 4 points

Problem Statement

You are given a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N) and an integer array A_1, A_2, \dots, A_N of length N.

A subset S of the set \lbrace 1,2,\dots,N \rbrace is called a good set if it satisfies the following condition:

  • For every pair of integers (x, y) such that x < y and x, y \in S, the following holds:
    • Let z be the integer such that P_z = \min(P_x, P_{x+1}, \dots, P_y). (Such a z is uniquely determined.) Then, it must hold that z \in S.

The cost of a good set S is defined as \displaystyle \sum_{i \in S} A_i.

For each K = 1, 2, \dots, N, find the minimum possible cost among all good sets of size K.

You are given T test cases. Solve each of them.

Constraints

  • 1 \leq T \leq 5000
  • 1 \leq N \leq 5000
  • 1 \leq A_i \leq 10^9
  • (P_1, P_2, \dots, P_N) is a permutation of (1,2,\dots,N)
  • The sum of N over all test cases is at most 5000
  • All input values are integers

Input

The input is given from standard input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
P_1 P_2 \dots P_N
A_1 A_2 \dots A_N

Output

Print T lines. For the i-th line, output the answer for the i-th test case.
For each test case, output the answers for K = 1,2,\dots,N in one line, separated by spaces.

Sample Input 1

3
4
4 1 2 3
1 8 2 4
6
5 3 2 4 6 1
73 38 30 85 27 45
10
4 10 3 7 2 6 8 9 5 1
853822501 687675302 281611653 844033520 423210108 339630584 780395612 207907746 285523486 359061085

Sample Output 1

1 6 11 15
27 57 95 140 213 298
207907746 493431232 833061816 1192122901 1537883577 1896944662 2584619964 3365015576 4209049096 5062871597

In the first test case:

  • For K=1, S=\lbrace 1 \rbrace is optimal,
  • For K=2, S=\lbrace 3,4 \rbrace is optimal,
  • For K=3, S=\lbrace 1,2,3 \rbrace is optimal,
  • For K=4, S=\lbrace 1,2,3,4 \rbrace is optimal.