시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 470 | 218 | 197 | 48.166% |
프로 은행강도 시우가 은행을 털려고 한다. 시우가 달려가는 일직선 경로 위엔 $N$개의 은행이 있다. $i$번째 은행은 직선상에서 서로 다른 좌표 $X_i$에 위치하며, 시간이 정확히 $T_i$ 일 때만 문이 열려 입장할 수 있다. 또한 이 은행을 털면 $C_i$원을 얻을 수 있다.
시우는 직선 상에서 임의의 정수 좌표에서 시작해 움직인다. 움직이는 동안 좌표는 증가해야 한다 (멈춰 설 수 없음에 주의하라). 시간은 $0$으로 시작하며 좌표가 $1$만큼 증가할 때 시간도 $1$만큼 증가한다.
시우는 문이 열려 있는 은행을 마주치면 반드시 털고 가며, 매우 숙련돼있기 때문에 은행을 털어도 시간이 전혀 증가하지 않는다.
시우가 적절한 위치에서 시작했을 때, 얻을 수 있는 최대 금액을 출력하여라.
첫 번째 줄에 $N$이 주어진다. ($1 \le N \le 300\,000$)
두 번째 줄부터 $N$개의 줄에 걸쳐 각 줄마다 $i$와 $X_i$가 증가하는 순서대로 정수 $X_i, T_i, C_i$가 주어진다. ($0 \le X_i, T_i, C_i \le 10^9$)
모든 $X_i$는 서로 다르다.
시우가 얻을 수 있는 최대 금액을 출력한다.
1 0 3 4
4
2 0 0 10 1 0 3
10
5 0 2 4 1 6 1 2 4 4 3 8 10 4 5 2
11