OCC '19 S5 - Partitioning

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 3.0s
Memory limit: 256M

Problem type

Michael has an array of N elements and Andrew has an array of K elements, which are sorted in non-decreasing order. Michael wants to show that his array is superior to Andrew's, but it's impossible to compare whose is greater if they are of different sizes. As such, Michael has decided that he will combine adjacent values in his array, creating a new element equal to the former two's sum in their place. He will perform this operation N-K times, so that in the end he will have K elements in his array. Michael will consider this array to be superior if when sorted in non-descending order each value is greater than or equal to the corresponding value in Andrew's array.

Formally, partition an array of N elements into K non-empty subarrays, such that when the sums of the values of each subarray, sorted in non-decreasing order, are each greater than or equal to its corresponding value in a second given array of K elements, or determine that this is not possible.


For all subtasks:

1 \le K \le N

1 \le N \le 2 \times 10^4

1 \le K \le \min(N, 11)

1 \le a_i \le 10^9

1 \le k_i \le 10^{14}

Subtask 1 [10%]

N \le 10^3 and K \le 2

Subtask 2 [15%]

N \le 10^4 and K \le 4

Subtask 3 [20%]

N \le 10^4 and K \le 8

Subtask 4 [55%]

No additional constraints.

Input Specification

The first line contains integers N and K, the number of elements in Michael's and Andrew's arrays, respectively. The second line contains N space-separated integers, Michael's array. The third line contains K space-separated integers, in non-decreasing order, Andrew's array.

Output Specification

If Michael can make his array superior to Andrew's, output YES on a single line. Otherwise, output NO.

Sample Input 1

5 2
10 3 5 2 7
4 9

Sample Output 1



There are no comments at the moment.