ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2123. Knapsack

hint
Posted by ironchat(ITMO) 9 Aug 2019 16:39
Simple solution, but try to optimize it!
If you want better explanation (myironmistake@gmail.com)
Re: hint
Posted by Harkonnen 13 Aug 2022 10:27
Simple recursion from highest weight down to lowest with proper cut-off on maximal reachable weight and caching of results gives AC in 0.015 sec and 1Mb RAM. I write that spoiler here because I suspects that tests are very weak because I have no proof of why this straightforward thing works so fast when problem has 4-sec/256Mb limits.