Edit

【pythonでABC195を解説】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()

プログラミング

-Edit