DOJ Beginner Contest 12 B - New City Planning
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 12
- 問題
- B - New City Planning
棟の建物を建てます。建物 の高さは 以上 以下の整数にでき、高さが の建物 1 棟につき、都市の完成度が 増えます。完成度の合計の最大値を求める問題です(、 として、全テストケースの の総和は 以下)。
建物どうしは影響し合わないので、建物ごとに完成度の増え方が最大になる高さを選べばよいです。建物 で得られる最大値は です。
の先頭からの最大値(累積 max) を前計算しておけば、答えは です。計算量は です。
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 始まりなので、 は B[a - 1] です。