для передачи сообщения по открытому каналу связи шифровальщики придумали сложный шифр. шифр состоит из n различных чисел, записанных в одну строку через пробелы. дешифрованное сообщение состоит из k чисел, которые являются номерами исходных чисел, разбивающих исходное сообщение на k частей (подпоследовательностей), так что сумма минимумов каждой подпоследовательности будет максимальна.

итак, от вас требуется написать программу, которая выполняет дешифровку заданного шифра.
формат ввода

первая строка входного файла содержит два разделенных пробелом натуральных числа n и к (1 ≤ k < n ≤ 300).

вторая строка входного файла содержит зашифрованное сообщение –n разделенных пробелом целых различных натуральных чисел а1, а2, а3… аn (1 ≤ ai ≤ 10).
формат вывода

выходной файл в первой строке содержит максимальную сумму к слагаемых, которые являются минимумами каждой части разбиения последовательности на k частей.

во второй строке выходного файла содержится дешифрованное сообщение из разделенных пробелом к натуральных чисел – номеров чисел в последовательности, которые завершают каждую из подпоследовательностей зашифрованного сообщения.

mishel7884    1   05.12.2019 10:39    10