레이팅 미적용FJ의 소 N마리(2 <= N <= 100,000)가 길고 곧은 1차원 울타리를 따라 여러 위치에 서 있다. i번째 소는 위치 x_i(0...1,000,000,000 범위의 정수)에 서 있으며, 무늬 없는 흰 소이거나 점박이 소이다. 같은 위치에 두 마리가 서 있는 경우는 없으며, 흰 소가 적어도 한 마리 있다.
FJ는 연속한 구간의 소들을 사진에 담고 싶은데, 사진 속 흰 소와 점박이 소의 수가 같아야 한다. 사진의 크기는 사진에 담긴 소들의 최대 위치와 최소 위치의 차이다.
더 큰 사진을 찍을 가능성을 높이기 위해 FJ에게는 페인트 한 통이 있어서, 흰 소들 중 임의의 부분집합에 점을 칠해 사실상 점박이 소로 만들 수 있다. 흰 소 일부에 페인트를 칠할 수 있다는 조건 아래, FJ가 찍을 수 있는 공정한 사진의 최대 크기를 구하라.
첫째 줄: 정수 N이 주어진다.
둘째 줄부터 1+N째 줄까지: i+1째 줄에는 x_i와 W(흰 소) 또는 S(점박이 소)가 주어진다.
흰 소 일부에 페인트를 칠해 점박이로 만들 수 있을 때, FJ가 찍을 수 있는 공정한 사진의 최대 크기를 출력한다.
fairphoto.in · 출력을 쓸 파일 fairphoto.out5
8 W
11 S
3 W
10 W
5 S7Output details: FJ photographs cows from position 3 to 10 (3 white, 1 spotted), painting one white cow.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > US Open > Silver