USACO 2014 US Open Contest Bronze Problem- 젖소 사진 찍기 > 문제은행 : 정보올림피아드&알고리즘




2791 : 젖소 사진 찍기

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
15 회   
시도횟수
211 회   

문제

농부 창재의 N마리의 젖소들은 직선 모양의 울타리에 서있다. 각 소들은 건지종이거나 홀스타인종이다.

 

농부 창재는 연속한 구간의 소들을 찍으려고 하는데 찍힌 사진에는 사진에 포함된 종류의 소들이 골고루 들어갔으면 한다. 즉, 홀스타인종의 소만 있는 사진이나 건지종의 소만 있는 사진은 찍을 수 있다. 두 종의 소들이 섞여 있는 경우에는 같은 수의 소들이 포함되어야 한다. 예를 들면 건지종의 소가 27마리 있고 홀스타인종의 소가 27마리 있는 사진은 찍을 수 있지만 건지종의 소가 10마리 있고 홀스타인종의 소가 9마리 있는 사진은 찍을 수 없다.

 

한편, 농부 창재는 농장의 광활함을 표현하기 위해 최대한 넓은 사진을 찍으려고 한다. 농부 창재를 도와 얼마나 넓은 사진을 찍을 수 있는지 구하는 프로그램을 작성하여라. 단, 사진의 양 끝에 젖소가 걸쳐있어야 한다.


입력형식

첫 번째 줄에는 젖소의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄부터 N개의 줄에는 각 소의 위치를 나타내는 0 이상 1,000,000,000 이하의 정수와 각 소의 종을 나타내는 문자(건지종이면 'G', 홀스타인종이면 'H')가 주어진다.

출력형식

농부 창재가 찍을 수 있는 가장 넓은 사진의 길이를 출력한다.

입력 예

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

출력 예

7

Hint!

3 ~ 10 범위의 소를 찍으면 건지종 소 2마리와 홀스타인종 소 2마리를 찍으면서 가장 넓게 찍을 수 있다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP