I think the time limit for the last Div 1 problem is a bit strict. My O(N log N) solution using C++ cin timed out, and after contest I used scanf and got accepted in about 2 seconds. This is not a long contest, so I think judge should allow 4x time of the optimized solution, which is currently 1 seconds. Some correct solutions timed out because of this.

There exists a Knuth Optimization like(for optimal binary tree problem) trick for this problem which I could find by guessing. Guess some relations for the "loop bounds" and verify them. If you need more hints, please tell.

I've seen many "Probability" and "Expected Value" related problems which can be solved using Gaussian method. 

Thanks for correcting.

Section 15.5 of "Introduction to Algorithms, 2nd Edition" (CLRS) describes an O(n³) algorithm for the Optimal BST problem. But it points in exercises that:

Exercises 15.5-4:
 Knuth has shown that there are always roots of optimal subtrees such that root[i, j - 1] ≤ root[i, j] ≤ root[i + 1, j] for all 1 ≤ i < j ≤ n. Use this fact to modify the OPTIMAL-BST procedure to run in Θ(n²) time.

I meant this optimization.

Hi,
 Thanks for your comment. Although it's not enough, but I already felt guilty after what happened. Of course, I'll contact you and talk with you as soon as possible.
 I hope you don't hate me.

Sorry, dp[i] = max(dp_1[i], ..., dp_n[i]). I wish comments were also editable :-)

Let dp[D+1] be the result before applying some group. We apply elements from this group independently on dp, to get arrays dp_1, ..., dp_n. Then we merge them, i.e. we choose dp[i] = max(dp_1[i], ..., dp_1[n]).

I wish you a happy new Iranian year too :-) Wish you a year full of rating increases and wins. Good luck.

Dear "acmer",
  Maybe I don't deserve to be a topcoder red, but after some inspection, I found some convincing clues about who you *really* are. Although, I guess you are not a single person, and a group of probably [2 .. 4] people. And probably you deserve to become a topcoder target, but you were unsuccessful in hiding yourself and leaving no clues.
 Some clues are:
   1. You posted this comment just after you registered, so I think this is not your real handle and you tried to hide yourself, so I guess you are someone I know.
   2. Registration of some person whom I know coincides with your registration off by some minutes (You can see the exact times in page sources of profile pages), let him call Mr. P1.
   3. Mr P1, and his friend Mr. P2 visited codeforces almost the same time of this comment, probably to "plus" it. I saw this comment 2 hours after it was posted, and their last visited time in their profile were almost same as this comment's. Again, I used page sources to extract exact times.

 Above clues, and some other clues lead me to guess who you really are.

 Furthermore, all of my posts were also minused just after your registration by at least two people, so I guess you and your friends might hate me. That's ok, but isn't more fair to talk with me directly instead of posting comments like this and minusing my post regardless of their content?

 Anyway, I don't understand your motives. But honestly when I first saw this comment, I didn't guess it could be you. I considered some other people before you.

  I am not sure to whom you are referring to, to Xazker or to me? Anyway we're both reds, and I don't see anything wrong by our being red there. I think the problem-set were easy for both of us, and we, along with many other red topcoders whom you may recognize, solved all problems.
  I am not sure who you are, but it seems that you just registered to insult and stay anonymous.

If we want to choose sometime so most people don't stay up much in the mid-night, 14:30 GMT might be good as it's 6:30 in Pacific time and 23:30 in Tokyo. But it overlaps with TCHS Finals, so probably you can choose 13:00 GMT which might not be a good time for some American/Canadians, or 18:00 which might not be good for some Asians.

By "straightforward implementation" I meant that I implemented exactly what problem statement said. I thought std::map is more natural as a database than an array or a std::vector, so what I meant by straightforward implementation takes O(n log n) time, not O(n^2). I did almost the same as Alias described.

Oh, I didn't notice the baby lion before. I feel somehow ashamed now. This reminds me of South Park episode Woodland Critter Christmas.