[초등부] 2025 KOI 1차대회 대비 모의고사 (4주차)

Byteburg의 동부 지역의 모든 건물은 오래된 건축 양식에 따라 서로 붙어있는 형태로 지어졌다.

즉, 건물 사이에 공간이 없다. 이러한 건물들은 동쪽에서 서쪽으로 이어지는 하나의 긴 건물 체인을 형성하며, 각 건물의 높이는 다를 수 있다.

Byteburg의 시장인 Byteasar는 이 건물 체인의 북쪽 면을 포스터로 덮는 작업을 계획하고 있다.

그는 최소한의 포스터 수로 전체 북쪽 면을 덮고 싶어 한다.

포스터는 직사각형 형태이며, 항상 수직 및 수평 변을 가지도록 배치해야 한다.

포스터는 겹쳐질 수 없지만, 맞닿을 수 있다. 즉, 서로의 변을 공유하는 것은 가능하다.

각 포스터는 반드시 특정 건물의 벽에 완전히 붙어야 하며, 전체 북쪽 면을 가려야 한다.

건물들의 높이 배열이 주어질 때, 최소한의 포스터 개수를 구하시오.

입력

표준 입력의 첫 번째 줄에는 체인을 구성하는 건물의 수를 나타내는 정수 n(1 ≤ n ≤ 250,000)이 하나 들어 있습니다.

그 다음 n개 줄에는 각각 단일 공백으로 구분된 두 개의 정수 d_i 와 w_i (1 ≤ d_i , w_i ≤ 1,000,000,000)가 들어 있으며, 각각 행의 i 번째 건물의 길이와 높이를 나타냅니다.

출력

표준 출력의 첫 번째이자 유일한 줄에는 건물의 북쪽 면을 덮기에 충분한 직사각형 포스터의 최소 개수를 나타내는 정수 하나가 포함되어야 합니다.

부분문제

포스터 붙이기
서브태스크

1초 1024MB