I didn't feel like doing dp today, so my submission to 1927G - Paint Charges is just the trivial integer programming formulation followed by a simple branch and bound algorithm.
In theory, this should be exponential; however, to my surprise, it passes test cases in less than 1/10 of the time limit. To me, it seems pretty difficult to generate test cases to avoid these types of submissions, since there are various branching strategies that one could apply.
Can anybody hack my solution? (And hopefully explain how to do that.)
Update: There are now ~70 more test cases namely the one that hacked my previous solution (test 91). That test breaks most solutions that branch blindly (or randomly). However if one uses an heuristic (like branching on the bigger values of $$$a_i$$$ first) its possible to not TLE on that specific case. To avoid the obvious hack of repeating test 91 ten times I also limited the number of nodes in the branch and bound search to a fixed number that fits on the time limit this can give WA but hasn't been hacked yet.
245269103 (passed system test)
I am sorry. (I used only $$$n = 100$$$ and $$$t = 1$$$). It works more than $$$15$$$ seconds.
Can you send me the test case? Or explain how you generated it?
I sent it!
The explanation is very simple! There is no test case that your code passed in which n > 100.
The problem constraints guarantee that $$$n \leq 100$$$.