I'm sorry to ask a foolish problem about my submission.So I share a way to solve 808E by ternary searching.
As we can see,W[i] = 1, 2, 3. We sort the Souvenirs which have the same W[i] by their C[i]. Then we know we will just choose a prefix for each W[i].
If we get X Souvenirs that W[i] = 3,we remain (m - 3X) to get Souvenirs that W[i] = 1, 2. Let's define F[i][x] the prefix sum of Souvenirs that W[i] = x. If we get Y Souvenirs that W[i] = 2,our cost is F[X][3] + F[Y][2] + F[m - 3X - 2Y][1] (m-3X-2Y>=0).
We can try every X and use ternary searching to find the best Y.The complexity is O(nlogn).
My submission:http://codeforces.me/contest/808/submission/27174539
But we know that as X increases,the optimal Y is decreasing,so you can use two-pointers to solve it.
And if you use radix sort,you can get an algorithm which complexity is O(n).
That's right!Thanks for your better solution.
打开CF回忆往事看到了熟悉的头像 这不会是ff吧 难道我在两年前就被ff回复过了？
emmm 是我是我
I'm trying to learn how to prove when a function (like this one) is strictly increasing-then-decreasing (or viceversa) so to apply ternary search. How can i formally show this function holds this property ??? Other problems are welcome too