시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB53252558.140%

문제

길이 $L$mm와 $R$mm의 두 관이 칸막이 하나를 사이에 두고 붙어있다.

안에는 총 $N$개의 입자들이 움직이고 있다.

$i$번 입자는 $x_i, d_i, w_i$의 세 수로 표현할 수 있다.

$x_i$는 입자의 초기 위치를 의미한다. 보다 구체적으로, $x_i > 0$이면 $i$번 입자는 칸막이로부터 오른쪽으로 $x_i - 1/2$ mm만큼 떨어져 있다는 의미이다. 반대로 $x_i < 0$이면 $i$번 입자는 칸막이로부터 왼쪽으로 $-x_i - 1/2$ mm만큼 떨어져 있다는 의미이다.

$d_i$는 입자의 초기 운동 방향을 의미하며, 1 또는 -1이다. 1이면 오른쪽으로, -1이면 왼쪽으로 운동하며 모든 입자는 같은 속력으로 움직인다. 입자는 관의 끝이나 닫힌 칸막이에 충돌하면 운동 방향이 반대로 바뀐다. 이때 속력은 유지된다. 입자끼리의 충돌은 고려하지 않는다.

$w_i$는 입자의 질량이다. 충돌이나 운동에는 역할을 하지 않는 변수이다.

우리의 목표는 적절한 시점에 칸막이를 임의로 열고 닫아 충분히 긴 시간이 흐른 후, 오른쪽 관에 있는 입자의 질량의 합을 최대화 하는 것이다. 칸막이에 동시에 부딪혀오는 입자들을 하나는 막고, 하나는 통과시키는 식으로 칸막이를 사용할 수는 없으나 칸막이를 여닫는 횟수나 간격에는 제한이 없다. 충분한 시간 이후 만들 수 있는 오른쪽 관의 입자 질량 합의 최댓값을 구하자.

입력

첫 줄에 $N, L, R$이 공백을 사이에 두고 주어진다. $(1 \le N \le 200,000, 1 \le L, R \le 10^9)$ 이후 $N$줄에 걸쳐 $i$번째 줄에는 $x_i, d_i, w_i$가 공백을 사이에 두고 주어진다. $(-L \le x_i \le -1$ 또는 $1 \le x_i \le R, 1 \le w_i \le 10^9)$

출력

충분한 시간 이후 만들 수 있는 오른쪽 관의 입자 질량 합의 최댓값을 출력하라.

예제 입력 1

6 4 2
1 -1 5
-1 1 6
-3 1 2
-4 -1 7
-2 1 3
2 -1 5

예제 출력 1

14

출처

High School > 경기과학고등학교 > 나는코더다 2021 송년대회 K번