|
|
WA on test 7. I've used uint64_t in array and sum, and int64_t in result. Corner case of sum = 0 is taken care of. Regards, So Sui Ming Simple solution, but try to optimize it! If you want better explanation (myironmistake@gmail.com) 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. Use 64 bit integer for resulting value. Initially I didn't believe result can be this big and spent a lot of time looking for another possible issues with code. |
|
|