Олимпиадный тренинг

Задача . Fair Photography


Задача

Темы: Префиксные суммы(минимумы, ...)

N коров (1 <= N <= 100,000) Фермера Джона стоят на различных позициях вдоль длинной прямой изгороди. I-ая корова стоит на позиции xi (целое число в диапазоне 0...1,000,000,000) и имеет породу Bi (‘G’ либо ‘H’). Никакие две коровы не занимают одну и ту же позицию.
ФД хочет сделать фото непрерывного интервала коров, но так чтобы породы были справедливо представлены на фото. Справедливо это значит, что все типы представлены одним числом, Например фото где все коровы имеют тип ‘H’ – подходит и фото где 27 ‘H’ и 27 ‘G’ тоже подходит, а фото с 10 ‘H’ и 9 ‘G’ – не подходит. Помогите ФД найти справедливое фото максимального размера. Размером фото называется разность между максимальной и минимальной позицией коров на фото. Возможно, что справедливое фото будет состоять из одной коровы, тогда ответ 0.
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит xi и bi.
Примечание
Имеется 6 коров с породами слева направо G, H, G, G, H, G.
Формат вывода:
* Строка 1: Одно целое число – максимальный размер справедливого фото.
Примечание
Наибольшее справедливое фото содержит 4 средних коровы, 2 ‘H’ и 2 ‘G’.
Примеры
№Входные данныеВыходные данные
1 
6
4 G
10 H
7 G
16 G
1 G
3 H
 
7
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет