4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс
Задача F. Сделайте неотрицательным!
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Тима считает массив целых чисел хорошим если все числа в массиве неотрицательные. У Тимы есть массив $a$ состоящий из $n$ целых чисел. Тима хочет сделать его хорошим, для этого он может делать следующую операцию:
- выбрать три целых числа $i,j, x$ такие, что $1 <= i,j <= n, i \ne j, 1 <= x <= 10^9$ и $a_i \ge x$, а затем из числа $a_i$ отнять $x$, а к числу $a_j$ прибавить $x$. Стоимость такой операции $|i - j| \cdot x$ тенге.
Формат входного файла
В первой строке находятся два целых числа $n, type (1 <= n <= 3 \cdot 10^5, 0 <= type <= 1)$.
Во второй строке находятся $n$ целых числа $a_1,a_2, ..., a_n(-10^8 <= a_i <= 10^8)$. Гарантируется, что можно сделать массив $a$ хорошим.
Формат выходного файла
В первой строке выведите минимальное количество тенге, которое необходимо чтобы сделать массив хорошим.
Если $type = 1$, во второй строке выведите одно целое число $k (0 <= k <= 2 \cdot n)$ — количество операции. В следующих $k$ строках выведите по три целых числа $i,j,x(1 <= i,j <= n, i \ne j, 1 <= x <= 10^9)$ — описания операций. Вам не надо минимизировать количество операций, но нужно минимизировать количество потраченных тенге.
Если $type = 0$, то кроме минимального количество тенге, ничего выводить не надо.
Система оценки
Задача состоит из восьми подзадач:
- Примеры из условия. Оценивается в 0 баллов.
- $n <= 10, type = 0, -1 <= a_i <= 1$. Оценивается в 8 баллов.
- $n <= 200, type = 0, -10 <= a_i <= 10, |a_1| + |a_2| + ... + |a_n| <= 400$. Оценивается в 16 баллов.
- $n <= 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 0$. Оценивается в 12 баллов.
- $n <= 2000, type = 0, -1 <= a_i <= 1$. Оценивается в 15 баллов.
- $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 1$. Оценивается в 13 баллов.
- $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8$. Оценивается в 15 баллов.
- $n <= 3 \cdot 10^5, type = 1, -10^8 <= a_i <= 10^8$. Оценивается в 21 баллов.
Примеры:
Вход 7 0 1 1 -1 0 -1 1 1Ответ
2Вход
4 1 4 -2 -2 1Ответ
5 3 1 2 2 1 3 1 4 3 1( Temirlan Satylkhanov )
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.