RiseOJ – 공정한 사진 (브론즈)

설명

농부 존의 소 N마리(1 <= N <= 100,000)가 길고 곧은 1차원 울타리를 따라 여러 위치에 서 있다. i번째 소는 위치 x_i(0...1,000,000,000 범위의 정수)에 서 있고 품종은 b_i이다('G'는 건지, 'H'는 홀스타인). 같은 위치에 두 마리가 서 있는 경우는 없다.

FJ는 연속한 구간의 소들을 사진에 담고 싶은데, 모든 품종이 공정하게 나오길 원한다. 따라서 사진에 어떤 품종들이 등장하든 각 품종의 수가 같아야 한다(홀스타인만 있는 사진도 괜찮고, 홀스타인 27마리와 건지 27마리가 있는 사진도 괜찮지만, 홀스타인 10마리와 건지 9마리가 있는 사진은 안 된다). 이 조건을 만족하는 사진의 최대 크기를 찾아 FJ를 도와라. 사진의 크기는 사진에 담긴 소들의 최대 위치와 최소 위치의 차이다. 소 한 마리만 담긴 사진의 크기는 0이다.

제약

입력 형식

첫째 줄: 정수 N이 주어진다.

둘째 줄부터 1+N째 줄까지: i+1째 줄에는 x_i와 b_i가 주어진다.

출력 형식

공정한 사진의 최대 크기를 정수 하나로 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 fairphoto.in · 출력을 쓸 파일 fairphoto.out

예제 1

입력

6
4 G
10 H
7 G
16 G
1 G
3 H

출력

설명

Output details: The largest fair photo is of the middle 4 cows, containing 2 Holsteins and 2 Guernseys.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > US Open > Bronze

올림피아드 > USACO > 2013-2014 > US Open > Bronze

태그

JudgeUSACO

공정한 사진 (브론즈)

평가 및 의견

풀이 제출