13263번: 나무 자르기
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 < a2 < ... < an, b1 > b2 > ... > bn을 만족
www.acmicpc.net
CHT 기초문제이다. 아래 자료를 먼저 읽고 온다면 도움이 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
def getX(f,g):
return (f[1]-g[1])//(g[0]-f[0])
def insert(x):
k.append(x)
while len(k)>2 and getX(k[-3], k[-2]) > getX(k[-2], k[-1]):
k.pop(-2)
def bs(x):
# print(k)
l = 0
r = len(k) - 1
while l<r:
mid = (l+r)//2
if getX(k[mid], k[mid+1]) <= x:
l = mid+1
else:
r = mid
return k[l][0] * x + k[l][1]
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp = [0] * n
k = [(b[0], 0)]
for i in range(1, n):
dp[i] = bs(a[i])
insert((b[i], dp[i]))
print(dp[n-1])
|
cs |
확실히 빠르게 작동한다.
'백준 문제풀이' 카테고리의 다른 글
| 백준 16895 - 님 게임 3 [Python] (2) | 2021.04.01 |
|---|---|
| 백준 17371 - 이사 [Python] (0) | 2021.04.01 |
| 백준 8911 - 거북이 [Python] (0) | 2021.03.29 |
| 백준 1655 - 가운데를 말해요 [Python] (0) | 2021.03.22 |
| 백준 21133 - N-Queen 2 [Python] (0) | 2021.03.12 |