## OCC '19 S5 - Partitioning

View as PDF

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

Author:
Problem type

Michael has an array of elements and Andrew has an array of 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 times, so that in the end he will have 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 elements into 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 elements, or determine that this is not possible.

and

and

and

#### Input Specification

The first line contains integers and , the number of elements in Michael's and Andrew's arrays, respectively. The second line contains space-separated integers, Michael's array. The third line contains 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.

5 2
10 3 5 2 7
4 9

YES