레이팅 미적용농부 존의 농장에 기록상 가장 더운 여름이 찾아와, 그는 소들을 시원하게 해줄 방법이 필요하다. 그래서 에어컨을 몇 대 들이기로 했다.
농부 존의 \(N\)마리 소(\(1 \leq N \leq 20\))는 \(1 \ldots 100\)으로 번호가 매겨진 일렬로 늘어선 칸들이 있는 헛간에 산다. 소 \(i\)는 칸 \(s_i\)부터 칸 \(t_i\)까지의 범위의 칸들을 차지한다. 서로 다른 소들이 차지하는 칸의 범위는 모두 서로 겹치지 않는다. 소마다 필요한 냉방량이 다르다. 소 \(i\)는 \(c_i\)만큼 시원해져야 하는데, 이는 소 \(i\)가 차지하는 모든 칸의 온도가 적어도 \(c_i\) 단위만큼 낮아져야 한다는 뜻이다.
헛간에는 \(1 \ldots M\)로 번호가 매겨진 \(M\)대의 에어컨이 있다 (\(1 \leq M \leq 10\)). \(i\)번째 에어컨은 가동하는 데 \(m_i\) 단위의 돈이 들고 (\(1 \leq m_i \leq 1000\)), 칸 \(a_i\)부터 칸 \(b_i\)까지의 범위의 칸들을 냉방한다. 가동 중이라면 \(i\)번째 에어컨은 이 범위의 모든 칸의 온도를 \(p_i\)만큼 낮춘다 (\(1 \leq p_i \leq 10^6\)). 에어컨이 냉방하는 칸의 범위는 서로 겹칠 수 있다.
농장을 운영하는 일은 쉽지 않기에 농부 존의 예산은 빠듯하다. 모든 소를 쾌적하게 유지하기 위해 그가 써야 하는 돈의 최솟값을 구하여라. 농부 존이 모든 에어컨을 가동하면 모든 소가 쾌적해짐이 보장된다.
Problem credits: Aryansh Shrivastava and Eric Hsu
Problem credits: Aryansh Shrivastava and Eric Hsu
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(N\)개의 줄은 소를 설명한다. 이 중 \(i\)번째 줄에는 \(s_i\), \(t_i\), \(c_i\)가 주어진다.
다음 \(M\)개의 줄은 에어컨을 설명한다. 이 중 \(i\)번째 줄에는 \(a_i\), \(b_i\), \(p_i\), \(m_i\)가 주어진다.
예제를 제외한 모든 입력에서 \(M = 10\)이라고 가정해도 된다.
위에 나열한 조건에 따라 모든 소를 만족시킬 만큼의 에어컨을 가동하기 위해 농부 존이 써야 하는 돈의 최솟값을 하나의 정수로 출력한다.
2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 510One possible solution that results in the least amount of money spent is to
select those that cool the intervals \([2, 9]\), \([1, 2]\), and \([6, 9]\), for a
cost of \(3 + 2 + 5 = 10\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > January > Bronze