コンテンツにスキップ

DOJ Beginner Contest 12 B - New City Planning

サイト
DOJ
コンテスト
DOJ Beginner Contest 12
問題
B - New City Planning

NN 棟の建物を建てます。建物 ii の高さは 11 以上 AiA_i 以下の整数にでき、高さが hh の建物 1 棟につき、都市の完成度が BhB_h 増えます。完成度の合計の最大値を求める問題です(1≤Ai,Bh≤1051 \le A_i, B_h \le 10^5、M=max⁡AiM = \max A_i として、全テストケースの N+MN + M の総和は 2×1052 \times 10^5 以下)。

建物どうしは影響し合わないので、建物ごとに完成度の増え方が最大になる高さを選べばよいです。建物 ii で得られる最大値は max⁡(B1,…,BAi)\max(B_1, \dots, B_{A_i}) です。

BB の先頭からの最大値(累積 max)Ch=max⁡(B1,…,Bh)C_h = \max(B_1, \dots, B_h) を前計算しておけば、答えは CA1+⋯+CANC_{A_1} + \dots + C_{A_N} です。計算量は O(N+M)O(N + M) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
for i in range(1, len(B)):
B[i] = max(B[i], B[i - 1])
print(sum(B[a - 1] for a in A))

B をその場で累積 max に書き換えています。リストは 0 始まりなので、CAiC_{A_i} は B[a - 1] です。