EduBrick
← вернуться к уроку · Практика: Бинарный поиск по массиву

Тройки с малой суммой

5000 мс · 256 МБ · всё или ничего

Дан список из nn чисел в произвольном порядке и число xx.

Сколько существует троек элементов с попарно разными номерами, сумма которых строго меньше xx? Тройки, отличающиеся только порядком, считаются одной.

Формат ввода

В первой строке числа nn от 33 до 10001000 и xx от 3109-3 \cdot 10^9 до 31093 \cdot 10^9. Во второй — nn чисел от 109-10^9 до 10910^9.

Формат вывода

Одно число.

Примеры

ввод
5 15
3 8 1 9 5
вывод
4

Примечание

Переберите первые два элемента тройки, а третий не перебирайте: посчитайте поиском, сколько подходящих стоит правее.

Войдите, чтобы отправлять решения.
← Вернуться к уроку