gautam94's blog

By gautam94, history, 7 years ago,

I tried doing it by finding the minimum removal cost for each score in and then using this to calculate the maximum total score by DP, but this is too slow. Any other ideas will be appreciated. Thanks.

• 0

 » 7 years ago, # | ← Rev. 4 →   0 do not understand why answer for second test case is -6. it should be -5. initial ratings are "-1 -2 -3 -4 -5" bribe first judge "1 3 3" and remove all ratings between 1 and 3 — "(-1 -2 -3) -4 -5" bribe second judge "3 4 4" and remove all ratings between 3 and 4 — "(-1 -2 [-3) -4] -5" there will be only one rating -5. UPD: Understand. The ith judge demanded Ci amount of money for removing each match
•  » » 7 years ago, # ^ | ← Rev. 4 →   +6 you can find minimal removal cost in N + M log M. const int K = 510 const int N = 10100 vector add[N]; vector del[N]; multiset m; ... for (int i = 0; i < m; ++i) { cin >> L >> R >> C; add[L].push_back(C); del[L].push_back(C); } m.insert(K); for (int i = 1; i <= N; ++i) { for (int j = 0; j < add[i].size(); ++j) m.insert(add[i][j]); minCost[i] = *m.begin(); for (int j = 0; j < del[i].size(); ++j) m.erase(m.find(del[i][j])); } 
•  » » » 7 years ago, # ^ |   0 I think you meant del[r].push_back(c) on line 11 instead of del[l].push_back(c) and the scores which don't lie inside any valid range can not be removed, so it should be m.insert(k+1) on line 14. I got AC with this code http://ideone.com/EJBqIN Thanks for helping.