xcx0902's blog

By xcx0902, history, 13 days ago, In English

Consider checking $$$k$$$ one by one. Let $$$sq$$$ be $$$\sum_{i=1}^n a_i$$$. For each $$$k \le sq$$$, calculate the strength in $$$O(n)$$$. For the other $$$k$$$, pre-calculate the contribution of $$$c_i \le sq$$$ (their contribution won't change when $$$k > sq$$$). Then we calculate each $$$c_i > sq$$$ (At most $$$sq$$$ occupation of $$$c_i$$$ that $$$c_i > sq$$$). So the total complexity is $$$O(n \cdot sq)$$$.

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, I did this and it surprisingly passed in 31 ms. I didn't actually precalculate it, i just iterated over all values higher than current k.