Submission #7082914


Source Code Expand

import bisect

INF = 10**10
n, W = map(int, input().split())
w = []
v = []
max_w = 0
max_v = 0
for i in range(n):
    v_, w_ = map(int, input().split())
    if max_v < v_:
        max_v = v_
    if max_w < w_:
        max_w = w_
    w.append(w_)
    v.append(v_)

# N <= 30
def solve1():
    global n, W, items
    # 半分全列挙
    a = n // 2
    b = n - a

    items1 = []
    items2 = []
    for i in range(2 ** a):
        w_ = 0
        v_ = 0
        for j in range(a):
            if i & 2**j > 0:
                w_ += w[j]
                v_ += v[j]
        items1.append([w_, v_])
    items1 = sorted(items1, key=lambda x: (x[0], -x[1]))
    for i in range(2 ** b):
        w_ = 0
        v_ = 0
        for j in range(b):
            if i & 2**j > 0:
                w_ += w[a+j]
                v_ += v[a+j]
        items2.append([w_, v_])
    items2 = sorted(items2, key=lambda x: (x[0], -x[1]))

    a_items = []
    pre_v = 0
    for i in range(len(items1)):
        if items1[i][0] > W:
            break
        if items1[i][1] > pre_v:
            a_items.append(items1[i])
            pre_v = items1[i][1]
    a_items.insert(0, [0, 0])

    b_items = []
    pre_v = 0
    for i in range(len(items2)):
        if items2[i][0] > W:
            break
        if items2[i][1] > pre_v:
            b_items.append(items2[i])
            pre_v = items2[i][1]
    b_items.insert(0, [0, 0])
    b_items.append([10**20, 0])
    b_w = [x[0] for x in b_items]

    ans = 0
    for i in range(len(a_items)):
        w_ = W - a_items[i][0]
        idx = bisect.bisect_left(b_w, w_) - 1
        if a_items[i][0] + b_items[idx][0] <= W:
            ans = max(ans, a_items[i][1] + b_items[idx][1])
        idx = bisect.bisect_left(b_w, w_)
        if a_items[i][0] + b_items[idx][0] <= W:
            ans = max(ans, a_items[i][1] + b_items[idx][1])
    print(ans)


# max_w <= 1000
def solve2():
    global n, W, items
    # wのdp
    dp = [[0 for _ in range(W+1)]for _ in range(n+1)]

    for i in range(n):
        for j in range(w[i], W+1):
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-1], dp[i][j - w[i]] + v[i])
    ans = 0
    for i in range(W+1):
        ans = max(ans, dp[-1][i])


# max_v <= 1000
def solve3():
    global n, W, items
    # vのdp
    sum_v = 0
    for i in range(n):
        sum_v += v[i]
    dp = [[INF for _ in range(sum_v+1)]for _ in range(n+1)]

    for i in range(n):
        dp[i][0] = 0
        for j in range(v[i], sum_v+1):
            dp[i+1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
    ans = 0
    for i in range(len(dp[-1])):
        if W >= dp[-1][i]:
            ans = i
    print(ans)

if n <= 30:
    solve1()
elif max_w <= 1000:
    solve2()
else:
    solve3()

Submission Info

Submission Time
Task D - ナップサック問題
User bluexleoxgreen
Language PyPy3 (2.4.0)
Score 34
Code Size 2836 Byte
Status WA
Exec Time 1260 ms
Memory 288828 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 34 / 34 0 / 33 0 / 33
Status
AC × 4
AC × 19
AC × 2
WA × 15
AC × 8
WA × 6
Set Name Test Cases
Sample subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask1 subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask2 subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt
Subtask3 subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt
Case Name Status Exec Time Memory
subtask00_sample_1.txt AC 164 ms 38256 KB
subtask00_sample_2.txt AC 403 ms 50288 KB
subtask00_sample_3.txt AC 170 ms 38256 KB
subtask00_sample_4.txt AC 167 ms 38256 KB
subtask01_0.txt AC 408 ms 50288 KB
subtask01_1.txt AC 411 ms 50288 KB
subtask01_10.txt AC 402 ms 50288 KB
subtask01_11.txt AC 410 ms 50416 KB
subtask01_12.txt AC 400 ms 50288 KB
subtask01_13.txt AC 406 ms 50416 KB
subtask01_14.txt AC 406 ms 50288 KB
subtask01_2.txt AC 403 ms 50288 KB
subtask01_3.txt AC 398 ms 50288 KB
subtask01_4.txt AC 294 ms 50160 KB
subtask01_5.txt AC 301 ms 50544 KB
subtask01_6.txt AC 297 ms 50160 KB
subtask01_7.txt AC 397 ms 50288 KB
subtask01_8.txt AC 403 ms 50288 KB
subtask01_9.txt AC 408 ms 50288 KB
subtask02_0.txt WA 847 ms 257672 KB
subtask02_1.txt WA 303 ms 69724 KB
subtask02_10.txt WA 297 ms 69724 KB
subtask02_11.txt WA 389 ms 105052 KB
subtask02_12.txt WA 585 ms 121308 KB
subtask02_13.txt WA 288 ms 39536 KB
subtask02_14.txt WA 366 ms 52060 KB
subtask02_2.txt WA 1061 ms 209720 KB
subtask02_3.txt WA 478 ms 66652 KB
subtask02_4.txt WA 957 ms 209720 KB
subtask02_5.txt WA 409 ms 50780 KB
subtask02_6.txt WA 933 ms 172232 KB
subtask02_7.txt WA 733 ms 121308 KB
subtask02_8.txt WA 504 ms 69724 KB
subtask02_9.txt WA 909 ms 172232 KB
subtask03_0.txt WA 1260 ms 288828 KB
subtask03_1.txt AC 1150 ms 257032 KB
subtask03_10.txt AC 859 ms 257032 KB
subtask03_11.txt AC 199 ms 39152 KB
subtask03_2.txt WA 855 ms 257032 KB
subtask03_3.txt WA 841 ms 257032 KB
subtask03_4.txt WA 857 ms 257032 KB
subtask03_5.txt WA 836 ms 257032 KB
subtask03_6.txt WA 793 ms 257032 KB
subtask03_7.txt AC 809 ms 257544 KB
subtask03_8.txt AC 805 ms 257672 KB
subtask03_9.txt AC 820 ms 257544 KB