시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 607 | 220 | 101 | 23.598% |
N 개의 광물이 있다. i 번째 광물은 (Xi , Yi )에 있으며 캐내는 비용은 1이고, 이것의 아름다운 정도는 Vi 이다.
호석이는 지금 (0, 0)에 있다. 타고난 광부인 호석이는 시그니쳐 스킬인 "광산 뒤집기"를 쓰려고 한다. 이 스킬을 쓰면 자신이 있는 위치를 꼭지점으로 하며, 원하는 높이 H(H ≥ 0), 너비 W(W ≥ 0) 인 직사각형 영역 안에 있는 모든 광물을 캘 수 있다. 영역의 테두리에 존재하는 광물도 캐야한다.
주의할 점은, 직사각형 영역 안에 들어오는 광물은 무조건 캐야 하며, 영역에 속한 광물들의 캐내는 비용의 총합이 현재 가진 돈 C 보다 크면 파산을 하게 된다.
호석이가 파산하면 광물을 못 캐고, 이로 인해 상상을 초월하는 나비효과가 발생해서 한국의 취직율이 떨어진다!!!!!!! 대신 호석이가 얻을 수 있는 광물들의 아름다운 정도의 합이 높아질수록 한국의 취직율은 올라간다!!!!!!!! 모두의 행복을 위해서 호석이가 파산하지 않고 얻을 수 있는 광물들의 아름다운 정도를 최대화하자.
첫 줄에 광물의 개수 N 과 호석이가 가진 돈 C 가 주어진다.
이어서 N개의 줄에 걸쳐서, i번째 줄에 3개의 정수 Xi , Yi , Vi 가 주어진다. 각 숫자는 i 번째 광물이 위치한 X, Y 좌표와 아름다운 정도를 의미한다.
호석이가 파산하지 않으면서 얻을 수 있는 광물들의 아름다운 정도의 합의 최댓값을 출력하라.
1 ≤ N ≤ 500,000
0 ≤ Xi , Yi ≤ 100,000
1 ≤ Vi ≤ 108
1 ≤ C ≤ N
광물들은 모두 서로 다른 위치에 존재하며, (0, 0) 에는 광물이 존재하지 않음이 보장된다. 주어지는 모든 수는 정수이다.
5 3 1 10 10 2 4 1 3 8 10 4 5 5 5 7 6
21
4 2 1 1 1 1 4 1 4 1 1 4 4 1
2
Contest > 류호석배 알고리즘 코딩 테스트 > 제2회 류호석배 알고리즘 코딩 테스트 5번