gautam94's blog

How to solve SPOJ CRICKDP
By gautam94, history, 9 years ago, In English

Problem: http://www.spoj.com/problems/CRICKDP/

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +6 Vote: I do not like it

    you can find minimal removal cost in N + M log M.

    const int K = 510
const int N = 10100
vector<int> add[N];
vector<int> del[N];
multiset<int> 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]));
}
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply