Bhaiya I’m getting WA in the Cover Them All! problem.
I’ve used this logic-
Case 1: b >= c
in this case the answer will simply be (y-x)*b, so total cost for this case is
sigma (y(i) - x) b
simplifying further, we get sigma (y) b - x b (number of soldiers having less bombs than current soldier)
To answer this one, we require 2 things:
- number of soldiers lying ahead having less bombs
- sum of their positions
this can be answered with segment tree / fenwick tree.
Case 2: b < c
total cost for this case is
sigma [(y(i) - x) * c(i)]
simplifying:
sigma [y(i) c(i)] - sigma [x c(i)]
= sigma [y(i) c(i)] - x (sigma c(i) )
the first term can be found out by precomputing all y(i)*c(i) values, and proceeding in a similar way
My code- https://ide.codingblocks.com/s/237452
@apaarkamal