most definitely hackable if N^3 due to no bounds over all tc
1e5*(1e2)^3 = 1e11 TLE
heres my O(n) sol instead note that only the last occourance of the largest element matters, lets start by reverse sorting it, for each element after it, it will go max-it-1, -1 because its after it so we can stop after making the max 0
if we move it before its max-it, so its +1 for each we move before
let x = arr_0
as long as this sum <= x, were fine, so we know what positions the last, now in a for loop lets fix the last max element occourance, making sure theres atleast occ(max) space in the prefix for other max elements to be, now do
npr for the max occourances * number of occourances (because were fixing it to the max which can be any element that is max) * (n-occ(max)-1)! for the rest of the elements
most definitely hackable if N^3 due to no bounds over all tc
1e5*(1e2)^3 = 1e11 TLE
heres my O(n) sol instead note that only the last occourance of the largest element matters, lets start by reverse sorting it, for each element after it, it will go max-it-1, -1 because its after it so we can stop after making the max 0
if we move it before its max-it, so its +1 for each we move before
let x = arr_0
as long as this sum <= x, were fine, so we know what positions the last, now in a for loop lets fix the last max element occourance, making sure theres atleast occ(max) space in the prefix for other max elements to be, now do
npr for the max occourances * number of occourances (because were fixing it to the max which can be any element that is max) * (n-occ(max)-1)! for the rest of the elements
and thats O(n) sol
here
355801103