[go: up one dir, main page]
Scribd
Upload
23 views2 pages

ArraySplitting (EN)

The document presents a problem from the INOI 2023 regarding splitting an array into at most K subarrays to minimize the maximum value of any subarray, where the array can contain negative numbers. It includes input specifications, output requirements, and constraints on the array's length and values. Sample inputs and outputs are provided to illustrate the problem's requirements.

Uploaded by

satan cat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
23 views2 pages

ArraySplitting (EN)

The document presents a problem from the INOI 2023 regarding splitting an array into at most K subarrays to minimize the maximum value of any subarray, where the array can contain negative numbers. It includes input specifications, output requirements, and constraints on the array's length and values. Sample inputs and outputs are provided to illustrate the problem's requirements.

Uploaded by

satan cat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

IOITC 2022 TST 2

Array Splitting
A participant went to take INOI 2023. When they opened the first question, they saw this as the statement:
There is an array A of length N. Split the array into at most K subarrays such that the maximum value
of any subarray is minimised. The value of a subarray is the sum of its elements.
At this point, the participant was very excited, but they frowned upon seeing the following line in the constraints:
The elements of the array are not guaranteed to be positive.
With INOI now over, the participant wants to know the solution to the problem. Can you help them?

Input
ˆ The first line contains two integers: N , the length of the array, and K, the maximum number of subarrays that
you can split the array into.
ˆ The second line contains N space-separated integers, A1 , . . . , AN .

Output
Print a single integer: the maximum value of any subarray if said value is minimised. Note that you do not need to
provide a construction to split the array.

Test Data
In all inputs,
ˆ 1 ≤ N ≤ 3 × 105
ˆ 1≤K≤N
ˆ −109 ≤ Ai ≤ 109

Subtask 1 (3 Points): Ai < 0 for all i.


Subtask 2 (7 Points): K = 2
Subtask 3 (15 Points): Ai > 0 for all i.
Subtask 4 (17 Points): N ≤ 80
Subtask 5 (18 Points): N ≤ 2000
Subtask 6 (40 Points): N ≤ 105

Sample Input 1
7 3
-3 4 12 -5 1 -2 1

Sample Output 1
6

1
Sample Input 2
6 2
-1 -3 4 -2 1 5

Sample Output 2
4

Sample Input 3
11 4
-4 1 3 -5 2 -1 6 0 -2 3 4

Sample Output 3
4

Sample Input 4
9 3
1 2 3 4 5 6 7 8 9

Sample Output 4
17

Limits
Time: 2 seconds
Memory: 256 MB

You might also like