n^2lgn,I think

O(n^2logn + qlogn)

If we implement only a simple knapsack for the problem then we wont get the optimum answer.Check this case

2

2 4 100

1 2 100

answer is 200 we can save object 2 and then save object 1.But we lose the number of the object after sorting.How can we get back the order??We can store the indices in a structure format or map them before sorting.I used structures because it was comfortable for me.My structure had t,d,p and then num(where t is time needed to save,d is time after which the object cant be saved,p is the value and num is the initial position of the object before sorting).

Hope this helps.Let me know if you have any difficulty.

I've just got an insight about problem E: Fire.

I believe that its plot is perfectly described in the scene youtube: "Quicksilver saving mutants from explosion in Xavier's school basement" // "X-Men: Apocalypse".

So my editorial is: imagine that d[i] + 1 is the time moment when explosion hits the i-th creature and try to be as good as Quicksilver even though his ways of always getting Σ p[i] did a fresh change to the problem overall perspective)))

Here is the screenshots for Chinese users (0.5 MB)

basically its about the order of choosing items . its better to choose the items first that will be burned sooner right ? because if you dont choose them fast (if its better to choose them) you probably cant choose them ever

http://mirror.codeforces.com/contest/864/submission/30745802

Console.ReadLine(); string a=Console.ReadLine();

I have the same error in my code. The issue with the order can be fixed through sorting. I assume you are sorting just based on the 'd' values. If so, then when 'd' is equal, the item with lower 't' value should come first. This solved the order disparity for me...however there is also a problem that while printing one item is skipped (I have the same problem too)...I have so far no idea why this happens.

Edit: The order might not be the real issue here...the answer is probably still valid. The main issue is the fact that one item is skipped while printing.

I couldn't catch the last two paras of the editorial, but here's what I understood-

Suppose we are at sj node currently. Now, consider all nodes connected to it with an edge, and let u be the lexicographically minimum among them, from which we can reach tj via dfs/bfs. Obviously it will be optimal to pick u. Because, from u we can still reach tj node from u-maybe at an infinite time(ie, never actually reach it). That is, we greedily select the next node. This gives us an n*q solution, what the last two paras did is to optimize this part.

I was also confused at first, but it makes sense if you think of all the values of dp as initially 0. So after initialization, it is just about upgrading the values of dp through those seemingly recursive relations.

I think NO is true because it consists of 4 different number, and there are just 2 girls.

Try out these cases, they were useful to debug my idea:

4 5 1 1 2 1 3 2 4 4 2 3 4 1 3 1 Ans = 1

4 5 1 1 2 1 3 2 4 3 4 4 2 1 3 1 Ans = 1

you may got the answer 20 in dp[3][20], because dp[3][20] = dp[2][0]+20 = dp[1][0]+20 = 20, and why we can simply solve this by sorting d was explained at before