Proof of greedy approach in 241C

Revision en1, by Ghost0fSparta, 2018-10-01 21:39:49

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.

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)