레이팅 미적용베시의 어린 사촌 엘라와 벨라가 농장에 놀러 왔다. 안타깝게도 이들은 도착한 이후로 말썽만 부리고 있다.
최근의 계략에서, 둘은 가능한 한 많은 풀을 깎기로 결심했다. 농장의 주요 초지는 큰 \(T \times T\) 정사각형 모양이다. 왼쪽 아래 꼭짓점은 \((0,0)\), 오른쪽 위 꼭짓점은 \((T,T)\)이다. 따라서 이 정사각형에는 \((T+1)^2\)개의 격자점(정수 좌표를 갖는 점)이 있다.
엘라와 벨라는 둘 다 \((0,0)\)에서 출발해 단위 속력으로 \((T, T)\)까지 달리며, 매우 날카롭고 매우 잘 늘어나는 철사의 양 끝을 각각 잡고 간다. 이 철사가 쓸고 지나간 모든 영역의 풀은 깎이게 된다. 엘라와 벨라는 서로 다른 경로를 택할 수 있지만, 각 경로는 격자점에서 격자점으로 이동하는 위쪽 및 오른쪽 걸음만으로 이루어진다.
베시는 풀이 너무 많이 깎일까 봐 걱정되어, 엘라와 벨라가 택하는 경로를 제한하는 영리한 계획을 고안한다. 초지 곳곳에는 \(N\)송이의 맛있는 꽃이 흩어져 있으며 (\(1 \leq N \leq 2 \cdot 10^5\)), 각 꽃은 서로 다른 격자점 위에 있다. 베시는 엘라와 벨라 둘 다 반드시 방문해야 하는 꽃들의 집합 \(S\)를 고른다(즉, 엘라의 경로는 \(S\)의 모든 꽃을 방문해야 하고, 벨라의 경로도 마찬가지이다). 이 경로들에 가능한 한 많은 경유지를 추가하기 위해, 베시는 \((0,0)\)에서 \((T,T)\)까지 위쪽과 오른쪽으로만 이동하는 소가 모두 방문할 수 있는 꽃 부분집합 중에서 가장 큰 것을 \(S\)로 택한다.
엘라와 벨라는 \(S\)의 꽃들을 방문해야 한다는 제약 아래에서 깎는 풀의 양을 최대화하려 한다. 깎이는 풀의 양이 가능한 한 작아지도록 베시가 \(S\)를 고르는 것을 도와주자.
문제 제공: Dhruv Rohatgi
문제 제공: Dhruv Rohatgi
첫째 줄에 \(N\)과 \(T\) (\(1 \leq T \leq 10^6\))가 주어진다. 다음 \(N\)개의 줄 각각에는 꽃의 정수 좌표 \((x_i, y_i)\)가 주어진다. 모든 \(i\)에 대해 \(1 \leq x_i, y_i \leq T-1\)이 보장되며, 어떤 두 꽃도 같은 수평선이나 수직선 위에 있지 않다.
적어도 20%의 테스트 케이스에서는 추가로 \(N \leq 3200\)이 보장된다.
깎이는 풀의 양의 최솟값을 나타내는 정수 하나를 출력한다.
mowing.in · 출력을 쓸 파일 mowing.out5 20
19 1
2 6
9 15
10 3
13 11117In the above example, it is optimal for Bessie to pick the flowers at \((10,3)\)
and \((13,11)\). Then in the worst case, Ella and Bella will cut three rectangles
of grass with total area \(117\).
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > February > Platinum