問題概要
問題ページ
-
-
D - Shipping Center
問題ページへ移動する
問題文
1 から N の番号がついた N 個の荷物と、1 から M の番号がついた M 個の箱があります。
荷物 i の大きさは W_i で、価値は V_i です。
箱 i には大きさが X_i 以下の荷物を入れることができます。1 つの箱に 2 つ以上の荷物を入れることはできません。
Q 個のクエリが与えられます。各クエリでは 2 つの整数 L,R が与えられるので、次の問題を解いてください。
- 問題：M 個の箱のうち、箱 L,L+1,\ldots,R の R-L+1 個の箱が使えなくなってしまいました。
残りの箱の中に同時に入れることができる荷物の価値の合計の最大値を求めてください。
制約
- 1 \leq N \leq 50
- 1 \leq M \leq 50
- 1 \leq Q \leq 50
- 1 \leq W_i \leq 10^6
- 1 \leq V_i \leq 10^6
- 1 \leq X_i \leq 10^6
- 1 \leq L \leq R \leq M
- 入力は全て整数
問題の考察
ACコード
import sys
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n, m, q = list(map(int, input().rstrip('\n').split()))
wv = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
x = list(map(int, input().rstrip('\n').split()))
query = [list(map(int, input().rstrip('\n').split())) for _ in range(q)]
wv.sort(reverse=True, key=lambda z: z[1])
for a, b in query:
ls = []
total = 0
for i in range(m):
if a - 1 <= i <= b - 1:
continue
else:
ls.append(x[i])
ls.sort()
for w, v in wv:
for i in range(len(ls)):
if ls[i] != -1:
if w <= ls[i]:
ls[i] = - 1
total += v
break
print(total)
if __name__ == '__main__':
solve()