Submission #69877779

---

Source Code Expand

import sys
input=sys.stdin.readline

n=int(input())
WV=[tuple(map(int,input().split())) for _ in range(n)]
q=int(input())
Q=[tuple(map(int,input().split())) for _ in range(q)]

CMAX=500
B=max(1,int(n**0.5))
nb=(n+B-1)//B
box=[[0]*(CMAX+1) for _ in range(nb)]

for b in range(nb):
  l=b*B
  r=min(n,(b+1)*B)
  dp=box[b]
  for i in range(l,r):
    w,v=WV[i]
    for c in range(CMAX-w,-1,-1):
      nv=dp[c]+v
      if nv>dp[c+w]:
        dp[c+w]=nv

def add_item(now,w,v,C):
  for c in range(C-w,-1,-1):
    nv=now[c]+v
    if nv>now[c+w]:
      now[c+w]=nv

def merge_block(now,blk,C,tmp):
  tmp[:C+1]=[0]*(C+1)
  for i in range(C+1):
    bi=now[i]
    if bi==0 and i!=0: continue
    rem=C-i
    for j in range(rem+1):
      nv=bi+blk[j]
      if nv>tmp[i+j]:
        tmp[i+j]=nv
  now[:C+1]=tmp[:C+1]

out=[]
now=[0]*(CMAX+1)
tmp=[0]*(CMAX+1)

for L,R,C in Q:
  L-=1; R-=1
  now[:C+1]=[0]*(C+1)
  bL=L//B; bR=R//B
  lEnd=min(R+1,(bL+1)*B)
  for i in range(L,lEnd):
    w,v=WV[i]
    if w<=C: add_item(now,w,v,C)
  if bL!=bR:
    rBeg=max(L,bR*B)
    for i in range(rBeg,R+1):
      w,v=WV[i]
      if w<=C: add_item(now,w,v,C)
  for b in range(bL+1,bR):
    merge_block(now,box[b],C,tmp)
  out.append(str(now[C]))

print("\n".join(out))

Submission Info

Judge Result