na982   5달 전

완벽한 nlogn으로 솔루션을 생각하지 못해서

size를 버킷을 만들어 정렬시킨후에, color를 가지고 정렬해서

200,000 * nlogn으로 풀었는데, 시간초과가 되네요;


어떤 방식으로 수정해서 풀어야 하는지 아이디어가 떠오르지 않네요; 고수분들 도움 요청 드립니다.

chan4928   5달 전

Prefix Sum

kalmiaa   5달 전

size 오름차순으로 sum값을 가지고 있으면 매번 size를 1까지 내리면서 합계를 계산할 필요가 없죠.

이제 같은색만 빼주면 되는데, 각 컬러볼마다 가능한(input으로 들어오는) size들을 push하고, lower_bound로 찾아가면 됩니다.

NlogN(20만*log(20000/2000) 으로 가능합니다.


저는 stl 안써서 속도가 느리네요..

댓글을 작성하려면 로그인해야 합니다.