Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Максимальная подпоследовательность

(Время: 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.TXTOUTPUT.TXTПояснение
18 12345678916409-12848 811 10440 -3399 8557 -5593 4943 -583
210 9999939145 13732 11797 -15720 -11775 -9501 -14849 8517 10711 -12649 7037

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 A. Чемпионат
 B. Дача
 C. Диофантово уравнение
 D. Максимальная подпоследовательность

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



VR клуб в СПБ