結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 961 ms
274,072 KB
testcase_01 AC 1,136 ms
274,052 KB
testcase_02 AC 1,175 ms
274,176 KB
testcase_03 AC 1,201 ms
273,804 KB
testcase_04 AC 1,172 ms
274,336 KB
testcase_05 AC 39 ms
52,736 KB
testcase_06 AC 49 ms
62,080 KB
testcase_07 AC 549 ms
203,944 KB
testcase_08 AC 706 ms
250,532 KB
testcase_09 AC 512 ms
197,584 KB
testcase_10 AC 582 ms
215,720 KB
testcase_11 AC 744 ms
252,492 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