Для даної послідовності \(a\), яка містить \(n\) цілих чисел у зростаючому порядку, трійка чисел (\(a_i, a_j, a_k\)) є красивою, якщо:
\(i < j < k\)
\(a_j - a_i = a_k - a_j = d\)
Підрахуйте кількість красивих трійок у послідовності \(a\).
Формат вхідних даних
Перший рядок вхідного потоку містить два цілі числа \(n,d\) (\(1 \le n \le 10^4\), \(1 \le d \le 20\)).
Наступний рядок містить елементи послідрвності \(a_i\) (\(0 \le a_i \le 2 \times 10^4\))
Формат вихідних даних
У вихідний потік вивести кількість красивих трійок.
Примітка
Красиві трійки: (1, 4, 7), (4, 7, 10), (2, 5, 8)
Приклад вхідних даних
7 3
1 2 4 5 7 8 10
Приклад вихідних даних
3
Коментарі
Добро дня. У мене є запитання та зауваження по цій задачі. Перше, ліміт на викнання одного блоку тестів - 1с. У задачі 8 блоків тестів, отже максимальний час виконання задачі - 8с. Але якщо відкрити "Кращі відправки", то можна побачити, що у користувача "Даринка" задача працює 8,01с, і вона зарахована. Чому так? Друге, я написав програму яка правильно рахує, але три останні блоки не проходила через ліміт часу, я її максимально оптимізував, і навіть переписав програму на C++, але все одно не проходить. Перевірте буль ласка тести починаючи із шостого. Дякую
Троє людей здало її на С++ і одна на Пайтоні. Правильно написане рішення чудово поміщається в обмеження. Проблема не в тестах)
Ти не зрозумів що я писав про того хто здав на Пайтоні, перечитай.
Time limit 1 с виділяється системою для роботи одного тесту для більшості мов програмування. Для Пайтона інколи ми окремо виділяємо більший час для тестування.
ps Зараз час для одного тесту 2 с і твій розв'язок отримує TL
Але в мене перші п'ять тестів працюють 0,005 с, чому починаючи із шостого вони не проходять?
Реалізований алгорит не приводить до повного розв'язку цієї задачі. Необхідно шукати метод розв'язання за меншу кількість проходів послідовності.