제출 #730036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730036		josanneo22	Knapsack (NOI18_knapsack)	Cpython 3	17 / 100	513 ms	10936 KiB

knapsack

from io import BytesIO, IOBase
import sys
import os
import bisect, collections, copy, heapq, itertools, math, sys
import time
import bisect
import functools
import math
import random
import re
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None


    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = sys.stdin.readline

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

inf = float('inf')

# from types import GeneratorType

# def bootstrap(f, stack=[]):
#     def wrappedfunc(*args, **kwargs):
#         if stack:
#             return f(*args, **kwargs)
#         else:
#             to = f(*args, **kwargs)
#             while True:
#                 if type(to) is GeneratorType:
#                     stack.append(to)
#                     to = next(to)
#                 else:
#                     stack.pop()
#                     if not stack:
#                         break
#                     to = stack[-1].send(to)
#             return to
#     return wrappedfunc

# RANDOM = random.getrandbits(32)

# class Wrapper(int):
#     def __init__(self, x):
#         int.__init__(x)

#     def __hash__(self):
#         return super(Wrapper, self).__hash__() ^ RANDOM

class SegmentTree:
    def __init__(self, data, merge):
        def _build(tree_index, l, r):
            if l == r:
                self.tree[tree_index] = data[l]
                return
            mid = (l + r) // 2
            left, right = 2 * tree_index + 1, 2 * tree_index + 2
            _build(left, l, mid)
            _build(right, mid+1, r)
            self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])

        self.n = len(data)
        self.tree = [None for _ in range(4 * self.n)]
        self._merge = merge
        _build(0, 0, self.n-1)

    def query(self, ql, qr):
        return self._query(0, 0, self.n-1, ql, qr)

    def _query(self, tree_index, l, r, ql, qr):
        if l == ql and r == qr:
            return self.tree[tree_index]

        mid = (l + r) // 2
        left, right = tree_index * 2 + 1, tree_index * 2 + 2
        if qr <= mid: return self._query(left, l, mid, ql, qr)
        elif ql > mid: return self._query(right, mid+1, r, ql, qr)

        return self._merge(self._query(left, l, mid, ql, mid),
                          self._query(right, mid+1, r, mid+1, qr))

    def update(self, index, value):
        def _update(tree_index, l, r, index):
            if l == r == index:
                self.tree[tree_index] = value
                return
            mid = (l + r) // 2
            left, right = 2 * tree_index + 1, 2 * tree_index + 2
            if index > mid: _update(right, mid+1, r, index)
            else: _update(left, l, mid, index)
            self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])

        _update(0, 0, self.n-1, index)

def merge(lst1, lst2):
    return max(lst1,lst2);

dp=[0]*100010
w=[0]*100010
c=[0]*100010
m=[0]*100010
new_n=-1
new_w=[0]*100010
new_c=[0]*100010
new_m=[0]*100010
C,n=MII()
for i in range(1,n+1):
    w[i],c[i],m[i]=MII()
new_n=0
for i in range(1,n+1):  
    j=1
    for j in range(1,(int)(math.log2(m[i]+1))):
        m[i]-=(1<<j)
        new_n+=1
        new_c[new_n]=(1<<j)*c[i]
        new_w[new_n]=(1<<j)*w[i] 
    if m[i]:
        new_n+=1
        new_c[new_n]=m[i]*c[i]
        new_w[new_n]=m[i]*w[i]
for i in range(1,new_n+1):
    for j in range(C,0,-1):
        if j-new_c[i]>=0:
            dp[j]=max(dp[j],dp[j-new_c[i]]+new_w[i])
print(dp[C])

• Subtask 1: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27