Problem - https://codeforces.com/contest/1257/problem/D
My solution - https://codeforces.com/contest/1257/submission/64891555 (Got tle, obviously)
- Sort the power array of heroes.
- Iterate from first to last on the monsters
- While calculating which monster to choose, I am applying a binary search to find index of heropower>= powerofMonster.
- Then I iterate all the vertices after that in linear time and choose the one which will kill maximum monsters.
Any help how can I optimize my approach further or would like to know how did you solve it?
I checked the submissions mostly I found out the segment tree approach but I don’t know it.
Would like to know your creative approach.