문제 5640 · 메가 I

끊김 없는 재생 목록

인증 제출 통계 · 5분마다 갱신 · 정답 비율 = 정답 제출 / 전체 제출
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1000ms / 테스트 (언어별 보정은 아래 표)	메모리: 측정하지 않음(브라우저 채점)	0	0	0	0.00%

문제

음악 스트리밍 서비스가 N곡이 나열된 추천 목록에서 일부를 골라 재생 목록을 만든다. i번째 곡에는 템포 a_i와 만족도 s_i가 있다. 만족도는 음수일 수 있는데, 광고가 섞인 곡이나 취향에 맞지 않는 곡이 그렇다. 재생 목록은 추천 목록에서 곡을 하나 이상 골라 원래 순서를 유지한 채 이어 붙인 것이다. 듣는 사람이 곡이 바뀔 때 어색함을 느끼지 않으려면 재생 목록에서 연이어 놓인 두 곡의 템포 차이의 절댓값이 D 이하여야 한다. 템포 차이가 D 이하인지는 바로 인접한 두 곡에 대해서만 확인하면 된다. 곡이 한 곡뿐인 재생 목록은 항상 조건을 만족한다. 이때 재생 목록에 포함된 곡들의 만족도 합이 최대가 되도록 할 때, 그 최댓값을 구하시오. 모든 곡의 만족도가 음수여도 곡을 최소 한 곡은 골라야 한다. 같은 템포의 곡이 여러 개 있을 수 있고, 만족도의 합은 32비트 정수 범위를 넘을 수 있다.

입력

첫 줄에 N과 D가 주어진다. (1 ≤ N ≤ 200,000, 0 ≤ D ≤ 10^9) 이어서 N개의 줄에 각각 a_i와 s_i가 주어진다. (1 ≤ a_i ≤ 10^9, -10^9 ≤ s_i ≤ 10^9)

출력

만족도 합의 최댓값을 한 줄에 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

-3

힌트 펼치기

dp[i]를 i번째 곡으로 끝나는 재생 목록의 최대 만족도로 정의하면 dp[i] = s_i + max(0, 앞선 곡 중 템포가 [a_i-D, a_i+D]에 있는 곡의 dp 최댓값)이다.
템포를 좌표 압축하고 구간 최댓값 질의와 점 갱신이 되는 세그먼트 트리를 쓴다.
답은 모든 dp[i] 중 최댓값이며, 전부 음수라면 가장 큰 단일 곡 값이 된다.

풀이 작성

연습 채점은 공개 테스트로 실행합니다. 인증 제출은 코드를 봉인한 뒤 새 입력을 실행하고 서버에서 출력을 대조하며 코드와 판정을 저장합니다.

풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.

연습 기록은 이 브라우저에 최근 50개를 저장합니다. 인증 기록은 내 제출에서 확인하세요.

이 브라우저의 연습 기록

언어별 제한

테스트 케이스마다 새 전역에서 실행하며 준비 시간은 제외합니다. 시간 초과된 출력은 검사하지 않습니다. 브라우저·기기 성능에 따라 실행 시간이 달라집니다.

언어	엔진(버전)	시간 제한	메모리
javascript	사용자 브라우저 JavaScript 엔진 (버전은 브라우저에 따라 다름)	1000ms / 테스트	측정하지 않음(브라우저 채점)
python	Pyodide 314.0.7 (CPython 3.14 WASM)	5000ms / 테스트	측정하지 않음(브라우저 채점)

문제

입력

출력