Home>
I want to confirm the mistake in the code that I thought about "Atcodr Beginner Contest 015 D Takahashikun's suffering"
Test case 36/47 is correct and 11 questions are incorrect.
Corresponding source codeW = int (input ())
N, K = map (int, input (). split ())
ab = [list (map (int, input (). split ())) for _ in range (N)]
dp = [[0] * (W + 1) for _ in range (N + 1)]
cnt = [[0] * (W + 1) for _ in range (N + 1)]
for i in range (N):
a, b = ab [i]
for j in range (W + 1):
if ja<0:
dp [i + 1] [j] = dp [i] [j]
cnt [i + 1] [j] = cnt [i] [j]
else: else:
if dp [i] [j]<dp [i] [ja] + b:
cnt [i + 1] [j] = cnt [i] [ja] +1
dp [i + 1] [j] = dp [i] [ja] + b
else: else:
cnt [i + 1] [j] = cnt [i] [j]
dp [i + 1] [j] = dp [i] [j]
ans = 0
for i in range (W + 1):
if cnt [N] [i]<= K:
ans = dp [N] [i]
print (ans)
What I tried
I've been learning dynamic programming recently, and I wondered if I could use the 2D DP table that often appears. Since there are many variables for constraints, I think that one 2D DP table is not enough, so I created a DP table with a variable name of cnt and counted the number of screenshots separately from the main DP table (variable name: dp). I wondered if it would work. The sample case passed without any problem, and the table seemed to be updated well, so I thought it would be a good idea, but it turned out to be test case WA. Is the idea wrong? Thank you.

Answer # 1
Related articles
 i have a question about basic python problems
 python  to make 6 question items in a set of 3 questions random
 python 3x  i have a question about sleep in python
 python 3x  "rgb triplets" atcoder abc162 inquiry about computational complexity
 python  [question] about combining pandas data frames
 python  atcoder bug not found [abc083b: some sums]
 python  regular expression wildcard? i have a question about
 python  tkinter photo image question
 i have a question about runtime errors and exception handling in python
 python 3x  i have a question about pipenv i want to set the directory location
 python 3x  "friends" atcoder abc177 code counterexample question (union find)
 python 3x  "colorful leaderboard" atcoder abc064 code counterexample
Trends
 python  you may need to restart the kernel to use updated packages error
 php  coincheck api authentication doesn't work
 php  i would like to introduce the coincheck api so that i can make payments with bitcoin on my ec site
 [php] i want to get account information using coincheck api
 the emulator process for avd pixel_2_api_29 was killed occurred when the android studio emulator was started, so i would like to
 javascript  how to check if an element exists in puppeteer
 python 3x  typeerror: 'method' object is not subscriptable
 i want to call a child component method from a parent in vuejs
 dart  flutter: the instance member'stars' can't be accessed in an initializer error
 xcode  pod install [!] no `podfile 'found in the project directory
If the number of sheets exceeds K, it cannot be used no matter how important the total is
In the current code, if the width is the same and the importance is high, it is updated without looking at the number of sheets at all, but with that, there are combinations that can not be used beyond K, and there are many sheets and it is not possible to increase the importance later, so the future potential Combinations without are likely to remain in the table.
Here's an example that doesn't work. try it.