레이팅 미적용농부 존은 베시의 다리마다 포고 스틱을 하나씩 달아 주었다. 이제 베시는 농장 곳곳을 빠르게 뛰어다닐 수 있지만, 아직 속도를 줄이는 법은 배우지 못했다.
베시의 훈련을 돕기 위해 농부 존은 일직선의 1차원 경로를 따라 연습 코스를 설치했다. 경로 위의 서로 다른 여러 위치에 베시가 착지해야 할 N개의 표적을 놓았다 (1 <= N <= 1000). 표적 i는 위치 x(i)에 있으며, 베시가 그 위에 착지하면 p(i)점을 얻는다. 베시는 원하는 아무 표적의 위치에서 출발하며, 한 방향으로만 이동할 수 있고, 표적에서 표적으로 뛰어다닌다. 각 점프는 이전 점프 이상의 거리를 이동해야 하며, 반드시 표적 위에 착지해야 한다.
베시는 밟은 모든 표적(처음 출발한 표적 포함)에 대해 점수를 얻는다. 베시가 얻을 수 있는 점수의 최댓값을 구하시오.
첫째 줄에 정수 N이 주어진다.
둘째 줄부터 1+N번째 줄까지, i+1번째 줄에 x(i)와 p(i)가 주어진다. 각각은 0..1,000,000 범위의 정수이다.
베시가 얻을 수 있는 점수의 최댓값을 출력한다.
pogocow.in · 출력을 쓸 파일 pogocow.out6
5 6
1 1
10 5
7 6
4 8
8 1025Output details: Bessie hops from x=4 (8 points) to x=5 (6) to x=7 (6) to x=10 (5).
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > November > Silver