레이팅 미적용농부 존에게는 편의상 \(1 \ldots M\)로 번호가 붙은 \(M\)마리의 소가 있는데, 이 소들은 가끔 풀 뜯기에서 벗어난 기분 전환을 즐긴다. 소들을 위한 간식으로 농부 존은 \(1 \ldots N\)로 번호가 붙은 \(N\)개의 파이(\(1 \leq N \leq 300\))를 구웠다. 소 \(i\)는 번호가 \([l_i, r_i]\) 범위(\(l_i\)부터 \(r_i\)까지, 양 끝 포함)에 있는 파이를 좋아하며, 정확히 같은 파이 범위를 좋아하는 두 소는 없다. 소 \(i\)는 또한 \(1 \ldots 10^6\) 범위의 정수인 무게 \(w_i\)를 가진다.
농부 존은 소들의 수열 \(c_1,c_2,\ldots, c_K\)를 선택할 수 있고, 선택된 소들은 그 순서대로 차례로 먹는다. 안타깝게도 소들은 나눠 먹을 줄 모른다! 소 \(c_i\)가 먹을 차례가 되면, 그 소는 자기가 좋아하는 파이를 전부, 즉 구간 \([l_{c_i},r_{c_i}]\)에 남아 있는 모든 파이를 먹어 치운다. 농부 존은 어떤 소가 먹을 차례가 되었는데 그 소가 좋아하는 파이가 이미 전부 먹혀 버린 곤란한 상황을 피하고 싶다. 따라서 수열의 각 소가 파이를 적어도 하나 먹는 수열 \(c_1,c_2,\ldots, c_K\) 중에서 가능한 최대의 총 무게(\(w_{c_1}+w_{c_2}+\ldots+w_{c_K}\))를 계산해 주기를 바란다.
문제 제공: Benjamin Qi
점수 배점
- 테스트 케이스 2-5는 \(N\le 50\)과 \(M\le 20\)을 만족한다.
- 테스트 케이스 6-9는 \(N\le 50\)을 만족한다.
문제 제공: Benjamin Qi
첫째 줄에 두 정수 \(N\)과 \(M\) \(\left(1\le M\le \frac{N(N+1)}{2}\right)\)이 주어진다.
다음 \(M\)개의 줄에는 각각 정수 \(w_i, l_i, r_i\)로 소 한 마리가 설명된다.
유효한 수열의 가능한 최대 총 무게를 출력한다.
pieaters.in · 출력을 쓸 파일 pieaters.out2 2
100 1 2
100 1 1200In this example, if cow 1 eats first, then there will be nothing left for cow 2 to eat. However,
if cow 2 eats first, then cow 1 will be satisfied by eating the second pie only.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > December > Platinum