Альтернативные суммы

@ARSENJ · Регистрация: 13.01.2020

Author24 — интернет-сервис помощи студентам

Альтернативной суммой (не менее двух) чисел b1, b2, b3,...,bn называется выражение
b1 − b2 + b3 − . . . ± bn (последнее слагаемое может быть как с плюсом, так и с минусом). Заданы
последовательность натуральных чисел и некоторые ее части. Нужно вычислить альтернативные
суммы заданных частей и из них найти наибольшую.
Формат входных данных
В первой строке даны два натуральных числа N и K, где 1 6 N, K 6 105
Во второй строке - N натуральных чисел a1, a2, a3,...,aN , каждое число не больше 2019.
В следующих K строках - по два натуральных числа p и q, 1 6 p<q 6 N, задающие последовательности из (q − p + 1) чисел ap,...,aq.
Формат выходных данных
Одно натуральное число - максимальная из альтернативных сумм по заданным последовательностям
Система оценки
В одном из тестов будет K 6 1000.
Пример
стандартный ввод стандартный вывод
5 2
12 15 22 8 5
1 3
2 5
19
Замечание
Пример: 12-15+22=19; 15-22+8-5=-4

@eaa · 18.01.2020, 13:32

И? что не получается конкретно?

Добавлено через 3 минуты
А сегодня же Всероссийская олимпиада школьников по информатике региональный этап. От туда чтоли задачи?

@ARSENJ · 19.01.2020, 13:30 **[ТС]**

да оттуда была

@eaa · 19.01.2020, 16:17

За O(n*k) примерно так:

Python

n, k = map(int, input().split())
a = list(map(int, input().split()))
m = -300000000
for _ in range(k):
    p, q = map(int, input().split())
    s = 0
    for i in range(p, q+1):
        s += a[i-1]*[1, -1][i % 2 == p % 2]
    m = max(m, s)
print(m)

Но задача имеет решение O(n + k), алгоритм не сложный.

@ARSENJ 0 / 0 / 0 Регистрация: 13.01.2020 Сообщений: 15
		1
	Альтернативные суммы 18.01.2020, 06:48. Показов 1257. Ответов 3 Метки нет (Все метки) Альтернативной суммой (не менее двух) чисел b1, b2, b3,...,bn называется выражение b1 − b2 + b3 − . . . ± bn (последнее слагаемое может быть как с плюсом, так и с минусом). Заданы последовательность натуральных чисел и некоторые ее части. Нужно вычислить альтернативные суммы заданных частей и из них найти наибольшую. Формат входных данных В первой строке даны два натуральных числа N и K, где 1 6 N, K 6 105 Во второй строке - N натуральных чисел a1, a2, a3,...,aN , каждое число не больше 2019. В следующих K строках - по два натуральных числа p и q, 1 6 p<q 6 N, задающие последовательности из (q − p + 1) чисел ap,...,aq. Формат выходных данных Одно натуральное число - максимальная из альтернативных сумм по заданным последовательностям Система оценки В одном из тестов будет K 6 1000. Пример стандартный ввод стандартный вывод 5 2 12 15 22 8 5 1 3 2 5 19 Замечание Пример: 12-15+22=19; 15-22+8-5=-4 0

@eaa Status 418 4578 / 2345 / 602 Регистрация: 26.11.2017 Сообщений: 5,265 Записей в блоге: 3
	18.01.2020, 13:32	2
	И? что не получается конкретно? Добавлено через 3 минуты А сегодня же Всероссийская олимпиада школьников по информатике региональный этап. От туда чтоли задачи? 0

@ARSENJ 0 / 0 / 0 Регистрация: 13.01.2020 Сообщений: 15
	19.01.2020, 13:30 [ТС]	3
	да оттуда была 0

	19.01.2020, 16:17