OCC '19 S5 - Partitioning

View as PDF

Submit solution

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

Author:
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 NK 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.

Constraints

For all subtasks:

1KN

1N2×104

1Kmin(N,11)

1ai109

1ki1014

Subtask 1 [10%]

N103 and K2

Subtask 2 [15%]

N104 and K4

Subtask 3 [20%]

N104 and K8

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

Copy
5 2
10 3 5 2 7
4 9

Sample Output 1

Copy
YES

Comments

There are no comments at the moment.