ํ์ด
</img>
์๊ฐ์ด๊ณผ์ ๋ฉ๋ชจ๋ฆฌ์ด๊ณผ๋ก ๊ต์ฅํ ์ ๋ฅผ ๋จน์๋ ๋ฌธ์ ์ ๋๋ค. ํ์ด์ฌ์ด ์ต์ํด์ง๋ฉด ์ด๋ฐ ๋ฌธ์ ๋ค๋ ์ฝ๊ณ ๋น ๋ฅด๊ฒ ํ ์ ์๊ฒ ์ฃ ?
์๊ฐ์ด๊ณผ ํด๊ฒฐ
(1) input
์ sys.stdin.readline
์ผ๋ก ์์ ํ์ต๋๋ค.
(2) Python
์ผ๋ก ๋๋ฆฌ๋ ์ฝ๋๋ฅผ PyPy3
์ผ๋ก ์์ ํด๋ณด์ธ์! ์กฐ๊ธ ๋ ๋นจ๋ผ์ง๋๋ค.
(3) 2์ค for loop์ ์ ๊ฑฐํ๊ณ ํ ๋ฒ๋ง ๋ณด์ ๋ฐฐ์ด์ ์ํํ๊ฒ ํ์ต๋๋ค. ์๊ฐ๋ณต์ก๋๋ฅผ ์๊ฐํด๋ณผ๊น์? N, K ๋ชจ๋ ์ต๋ 300,000๊น์ง ๋ค์ด์ค๋ฏ๋ก ํธ์๋ฅผ ์ํด N๊ณผ K๋ฅผ ๋ฌถ์ด์ N์ด๋ผ๊ณ ์๊ฐํด๋ณด๊ฒ ์ต๋๋ค. ๋๋ต 10^8์ ์ฐ์ฐ์ ์ฒ๋ฆฌํ๋ ๋ฐ์ 1์ด๊ฐ ์๋ชจ๋ฉ๋๋ค. ํด๋น ๋ฌธ์ ์ ์๊ฐ์ ํ์ 1์ด์๊ณ , 2์ค for loop์ ๋๊ฒ ๋๋ฉด O(N^2)์ด๋ฉฐ, N์ 3(10^5)์ด๋ฏ๋ก N^2์ 9(10^10)์ด ๋ฉ๋๋ค. ๋๋ต 10^11 ์ ๋ ๋๊ฒ ๋ค์. ์ด๋ ๋ถ๋ช
ํ 1์ด ๋ด์๋ ์ฒ๋ฆฌํ ์ ์๋ ์์
๋๋ค. ์๋ง 100,000์ด ์๋๋ผ ์ ๋งคํ๊ฒ 300,000์ผ๋ก ์ค์ ํ์ ๊ฒ๋ ๋ฐ๋์ NlogN์ผ๋ก ํ๊ฒ๋ ํ๋ ค๋ ์๋์ธ ๋ฏ ํฉ๋๋ค.
๋ฉ๋ชจ๋ฆฌ์ด๊ณผ ํด๊ฒฐ
(1) heapq์ ๋ค์ด๊ฐ๋ ์ค๋ณต์ ์์ด์ต๋๋ค. ํ ๋ฒ๋ง ๋ณด์ ๋ฐฐ์ด์ ์ํํ๊ฒ ํ๋ฉด์, ์ง์ ๊ฐ๋ฐฉ์์ ํ์์ด ๋๋ ๊ณณ๋ถํฐ ๋ค์ ์ํํ๊ฒ ๋ฐ๊พธ์ด์ฃผ์์ต๋๋ค. ์ด๋ป๊ฒ ์ด๊ฒ ๊ฐ๋ฅํ๊ฑธ๊น์? ๊ฐ๋ฐฉ ๋ฐฐ์ด์ ๋ฌด๊ฒ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ ๊น๋ญ์ ๋๋ค. ์ต๋ ์ค๋ 2์ธ ๊ฐ๋ฐฉ์ด ๋ด์ ์ ์๋ ๋น์ผ ๋ณด์๋ค์, ๋น์ฐํ ์ต๋ ์ค๋ 10์ธ ๊ฐ๋ฐฉ๋ ๋ด์ ์ ์์ผ๋ ์๋กญ๊ฒ heap์ ๋ฃ์ด์ค ํ์๊ฐ ์์ต๋๋ค.
์ฝ๋
import heapq
N, K = map(int, input().split())
jew = [list(map(int, input().split())) for _ in range(N)] # m, v
bag= [int(input()) for _ in range(K)]
jew = sorted(jew, key=lambda x : x[0])
bag.sort()
ans = 0
h = []
j_idx = 0
for b in bag :
while(True) :
if(j_idx >= N) :
break
j = jew[j_idx]
if(j[0] <= b) :
heapq.heappush(h, -j[1])
j_idx+=1
else :
break
if(h) :
ans -= heapq.heappop(h)
print(ans)