Proof of greedy approach in 241C

Revision en2, by Ghost0fSparta, 2018-10-02 04:53:17

Hello cf, according to the editorial of 241C problem the group which will pay maximum should be assigned to the smallest sized table to which it can fit. Can anybody prove this is optimal strategy?
Also the problem has a tag of dp, so how to solve this problem using dp?
Any help is highly appreciated.

Those who are downvoting the post should kindly state why in the comments. According to me this is a perfectly valid question and I can't understand why are people downvoting it. Let me guess. Yes, they are a**holes.

Tags codeforces round #241, greedy, #dp, proof

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Ghost0fSparta 2018-10-02 04:53:17 228 Tiny change: 'e a**holes.' -> 'e a**holes'
en1 English Ghost0fSparta 2018-10-01 21:39:49 437 Initial revision (published)