GAECHKA
Твоя помощница в решении задач

Поезд

поезд


Обсуждаемый нами поезд состоит из локомотива и N вагонов (с номерами от 1 до N, начиная с локомотива). В каждом вагоне есть известное количество пассажиров (отметим Vi количество пассажиров в вагоне I. Пассажирам не разрешается путешествовать из одного вагона в другой.
Локомотив вышел из строя, и для доставки вагонов к месту назначения можно использовать 3 миниламотомива, привезенных с ближайшей железнодорожной станции. Мини-вагон может тянуть небольшое количество вагонов (максимум М), и, как правило, трех мини-вагонов недостаточно, чтобы вытащить все вагоны, из которых сделан поезд. Мини-локомотив может тянуть последовательность вагонов (последовательных вагонов поезда). Последовательность вагонов, которую тянет мини-локомотив 1, не должна примыкать к последовательности вагонов, запряженных мини-локомотив 2. Минилокомотив 2 может тянуть на мертвой линии вагоны, расположенные между последним вагоном, запряженным локомотивом 1, и первым вагоном, который локомотив 2 намеревается доставить к месту назначения. Аналогично, последовательность вагонов, запряженных мини локомотив 2. не должна примыкать к последовательности вагонов запряженных minilocomotiva 3.

Напишите программу, чтобы определить максимальное количество пассажиров, которые могут быть доставлены к месту назначения на 3 мини-автомобилях.


Входной файл tren.in.txt содержит в первой строке натуральное число N, представляющее количество вагонов.
Вторая строка содержит N натуральных чисел, разделенных пробелом, v1, v2... vN представляющих количество пассажиров в каждом вагоне. третья строка содержит натуральное число M, представляющее максимальное количество вагонов, которые может тянуть мини-локомотив.

Выходной файл tren.out.txt содержит одну строку с максимальным количеством пассажиров, которых можно перевозить с помощью 3 минилокомотивов.


1 ≤ M ≤ N ≤ 50000
vi<=100, 1
пример

tren.in.txt
7
35 40 50 10 30 45 60
2



tren.out.txt
240
0
вопрос задан

Источник


0 ответов