FPC23-011.Industry Improvements
Easy · 2 s · 256 MB
- icpc
- fpc
- 2023
As a member of the Factory Planning Committee, you are responsible for overseeing the production process and ensuring that everything runs smoothly.
The committee aims to guarantee efficient processing of boxes by the machines in the production line without breakdowns. You recognise that a machine is more prone to breaking down when handling heavier objects, and therefore, propose to set a maximum weight capacity for the machines. Considering budget constraints, the committee also agrees to limit the number of times a machine can be started to no more than times.
Your task is to determine the minimum weight capacity required for a machine line to process all boxes, while ensuring that the machine line is started no more than times and the boxes are processed in the given order.
As an example, consider the first sample input. We can process all boxes by splitting the boxes in these three contiguous subsequences:
With this split, the capacity of the machine needs to be units of weight.
Giriş formatı
The input consists of:
• One line with two integers and (, ), the number of boxes and the number of times the machine can be started.
• One line with integers (), the weights of the boxes, in the order in which they need to be processed.
Çıxış formatı
Output the minimum weight capacity required by the machine to process all boxes within runs or less.
Qeyd
Source: Freshmen Programming Contest 2023 · Author: Cristian-Alexandru Botocan · License: CC BY-SA 4.0 · Original: https://fpc.wisv.ch · Statement adapted for AlgoLens and shared under the same license. · 4 of the 31 original test cases (the largest) are omitted here to keep the problem lightweight.
Nümunələr
Giriş #1
6 3 7 3 2 3 1 4
Çıxış #1
8
Giriş #2
4 1 11 18 3 10
Çıxış #2
42
Giriş #3
5 3 123456789 987654321 111111111 555555555 444444444
Çıxış #3
1098765432