페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5319

사과 잡기 (Apple Catching) 2초 256MB

문제

사과 비가 내리고 있다. 

특정 시점에 몇 개의 사과가 번호 표시줄에 떨어진다. 

어느 시점에 소 중 일부는 번호 표시줄​​에 도착하여 사과를 잡는다.

 

사과가 소에게 잡히지 않고 번호 표시줄에 떨어지면 해당 사과는 영원히 사라진다. 

소와 사과가 동시에 도착하면 소가 그것을 잡는다. 

각 소는 초당 1단위의 위치를 이동할 수 있으며, 소가 사과 한 개를 잡으면 번호 표시줄​을 빠져 나온다.

 

소가 최적으로 이동하면 총 몇 개의 사과를 잡을 수 있는지 출력하시오.​ 


입력

입력의 첫 번째 줄에는 사과가 번호 표시줄​​에 떨어진 횟수 또는 농부 존의 소가 나타난 횟수인 N(1 ≤ N ≤ 2⋅10^5)이 입력된다.

다음 N 줄은 각각 4개의 정수 q_i, t_i, x_i 및 ni가 입력된다(q_i ∈ \{1,2\}, 0≤t_i≤10^9, 0≤x_i≤10^9, 1≤n_i≤10^3).

q_i=1이면 농부 존​의 n_i마리 소가 시간 t_i에서 번호 표시줄​의 x_i 위치에 온다는 의미한다.

q_i=2이면 n_i개 사과가 시간 t_i에서 번호 표시줄​​의 x_i 위치에 떨어졌음을 의미한다​.

입력은 모든 순서쌍(t_i,x_i)이 고유함을 보장한다.​


출력

농부 존​의 소가 잡을 수 있는 최대 사과 수를 출력하시오.


예제1

입력
5

2 5 10 100

2 6 0 3

2 8 10 7

1 2 4 5

1 4 7 6
출력
10

이 예에서는 t=5에 떨어진 사과 100개 중 어느 것도 잡을 수 없습니다. 사과 10개를 잡는 방법은 다음과 같습니다.

​- t=4에 도착한 소 6마리는 모두 t=8에 ​떨어진사과를 잡는다.​

​- t=2에 도착한 소는 t=8에 ​떨어진사과를 잡는다​.

​- ​t=2에 도착한 나머지 세 마리의 ​소는 각각 t=6에 떨어진 사과를 잡는다​.


예제2

입력
5

2 5 10 100

2 6 0 3

2 8 11 7

1 2 4 5

1 4 7 6
출력
9

이번에도 t=5에 떨어진 사과는 잡을 수 없습니다. 또한 t=2에 도착한 소는 t=8에 도착한 사과를 잡을 수 없었습니다. 사과 9개를 잡는 방법은 다음과 같습니다.

- t=4에 도착한 소 6마리는 모두 t=8에 떨어진 사과를 잡는다. - t=2에 도착한 나머지 세 마리의 소는 각각 t=6에 떨어진 사과를 잡는다.​



출처

USACO 2022 US Open Gold

역링크 공식 문제집만