結果

問題 No.2741 Balanced Choice
ユーザー sk4rdsk4rd
提出日時 2024-04-20 18:28:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,185 ms / 2,000 ms
コード長 3,200 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 274,332 KB
最終ジャッジ日時 2024-04-20 18:28:26
合計ジャッジ時間 10,524 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 933 ms
274,332 KB
testcase_01 AC 1,111 ms
274,188 KB
testcase_02 AC 1,167 ms
273,920 KB
testcase_03 AC 1,185 ms
274,060 KB
testcase_04 AC 1,153 ms
274,200 KB
testcase_05 AC 36 ms
53,700 KB
testcase_06 AC 45 ms
63,660 KB
testcase_07 AC 564 ms
203,812 KB
testcase_08 AC 704 ms
250,536 KB
testcase_09 AC 509 ms
197,568 KB
testcase_10 AC 592 ms
215,984 KB
testcase_11 AC 741 ms
252,500 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Array2d:
    def __init__(self, h, w, init_v = 0, out_v = None):
        self.h, self.w = h, w
        self.data = [init_v] * (h*w)
        self.out_v = out_v
    def __call__(self, data): # build with 2d-list
        assert len(data) == self.h
        for i in range(self.h):
            assert len(data[i]) == self.w
            for j in range(self.w):
                self.data[i*self.w+j] = data[i][j]
    def get(self, i, j):
        if i < 0 or j < 0 or i >= self.h or j >= self.w: return self.out_v
        return self.data[i*self.w+j]
    def set(self, i, j, value):
        if i < 0 or j < 0 or i >= self.h or j >= self.w: return False
        self.data[i*self.w+j] = value
        return True
    def __getitem__(self, idx):
        assert type(idx) == tuple
        i, j = idx
        return self.get(i, j)
    def __setitem__(self, idx, value):
        assert type(idx) == tuple
        i, j = idx
        self.set(i, j, value)
    def dmp(self, sep=" "):
        res = ""
        for i in range(self.h):
            res += sep.join(map(str, self.data[i*self.w:(i+1)*self.w])) + "\n"
        return res
    def __str__(self):
        return self.dmp()
    def all(self, y1, x1, y2, x2, val):
        assert y1 <= y2
        assert x1 <= x2
        if y1 < 0 or y2 > self.h: return False
        if x1 < 0 or x2 > self.w: return False
        for y in range(y1, y2):
            for x in range(x1, x2):
                if self.data[y*self.w+x] != val:
                    return False
        return True
    def fill(self, y1, x1, y2, x2, val):
        assert y1 <= y2
        assert x1 <= x2
        if y1 < 0 or y2 > self.h: return False
        if x1 < 0 or x2 > self.w: return False
        for y in range(y1, y2):
            for x in range(x1, x2):
                self.data[y*self.w+x] = val
    def rotate(self):
        assert self.h == self.w
        tmp = [None] * (self.h*self.w)
        for i in range(self.h):
            for j in range(self.w):
                tmp[(self.w-j-1)*self.w+i] = self.get(i, j)
        self.data = tmp

N, W, D = map(int, input().split())
item1, item2 = [], []
for _ in range(N):
    t, w, u = map(int, input().split())
    if t: item2.append((w, u))
    else: item1.append((w, u))

n, m = len(item1), len(item2)

dp1 = Array2d(n+1, W+1)
dp2 = Array2d(m+1, W+1)

for i in range(n):
    weight, value = item1[i]
    for j in range(W+1):
        if j >= weight:
            if dp1[i, j-weight] > 0 or (j-weight == 0):
                dp1[i+1, j] = max(dp1[i, j], dp1[i, j-weight]+value)
        dp1[i+1, j] = max(dp1[i+1, j], dp1[i, j])

    
for i in range(m):
    weight, value = item2[i]
    for j in range(W+1):
        if j >= weight:
            if dp2[i, j-weight] > 0 or (j-weight == 0):
                dp2[i+1, j] = max(dp2[i, j], dp2[i, j-weight]+value)
        
        dp2[i+1, j] = max(dp2[i+1, j], dp2[i, j])

#print(dp1); print(dp2)

ans = 0
for i in range(W+1):
    for j in range(W+1):
        if abs(i-j) > D or i+j > W: continue
        if i > 0 and dp1[n, i] == 0: continue
        if j > 0 and dp2[m, j] == 0: continue
        #print(i, j, dp1[n, i] + dp2[m, j])
        ans = max(ans, dp1[n, i] + dp2[m, j])

print(ans)
0