Максимальная подпоследовательность
(Время: 2 сек. Память: 32 Мб Сложность: 43%)
Задан числовой целочисленный массив A[1..N], замкнутый в кольцо так, что его последний и первый элементы являются соседними. В этом массиве необходимо найти такую непрерывную непустую подпоследовательность, сумма элементов которой максимальна. Содержимое массива будем получать из последовательности псевдослучайных чисел.
Последовательность 31-битных псевдослучайных чисел R31 определена следующим образом: R31[0] задано во входных данных, последующие значения вычисляются по формуле:
R31[i] = (R31[i-1]*1103515245+12345) mod 231, 1 ≤ i ≤ N, где mod - операция остатка от деления.
Элементы массива определяются следующим образом:
A[i] = R31[i] div 216 - 214, 1 ≤ i ≤ N, где div - операция целочисленного деления.
Входные данные
Входной файл INPUT.TXT содержит два числа, разделённых пробелами: N – размер массива (1 ≤ N ≤ 108) и R31[0] (0 ≤ R31[0] < 231).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – сумму элементов искомой подпоследовательности.
Примеры
№ | INPUT.TXT | OUTPUT.TXT | Пояснение |
1 | 8 123456789 | 16409 | -12848 811 10440 -3399 8557 -5593 4943 -583 |
2 | 10 99999 | 39145 |
13732 11797 -15720 -11775 -9501 -14849 8517 10711 -12649 7037
|
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|