Задача к ЕГЭ по информатике на тему «Цепочки, выбор последовательности, префиксные суммы» №4

Просмотров 8 Комментарии 0

Дано число $N$ , затем последовательность из $N$ целых чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел кратно $10$ . Найдите наибольшую сумму такой последовательности.

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке одно натуральное число $N (1 ≤ N ≤ 1000000)$ — количество чисел. Каждая из следующих $N$ строк содержит целое число. В ответе запишите значение искомой суммы сначала для файла A, затем для файла B через пробел.

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = -1000000000
for i in range(n):
    cnt = 0
    sum = 0
    for j in range(i, n):
        sum += a[j]
        if a[j] < 0:
            cnt += 1
        if cnt % 10 == 0:
            ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

file = open(’27B.txt’, ’rt’)
n = int(file.readline())

s = 0
k = 0
mps = [0] + [10000000 for _ in range(9)]
ans = -1000000

for i in range(n):
    x = int(file.readline())
    s += x
    if x < 0:
        k += 1
    ans = max(ans, s - mps[k % 10])
    mps[k % 10] = min(mps[k % 10], s)
print(ans)

Ответ: 394 243750