e-olymp
Соревнования

February 21 - March 3. Dynamic Programming

Скобки

Рассмотрим скобочные последовательности с одним типом скобок. Для заданной скобочной последовательности найдите количество ее подпоследовательностей, которые являются правильными скобочными последовательностями.

Например, для последовательности "((())())(" таких последовательностей восемь: "((())())", "(())()", "((()))", "(()())", "(())", "()()", "()" и "".

Входные данные

Содержит последовательность, состоящую не более чем из 300 круглых скобок.

Выходные данные

Выведите количество различных правильных скобочных подпоследовательностей заданной последовательности.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
((())())(
Выходные данные #1
8