You are the curator of a prestigious art exhibition. You have paintings, each with two attributes: painting size and artistic value . You also have available frames, each with frame size .
You want to select and arrange paintings and frames for display such that:
Each selected painting is placed in frame where the painting size does not exceed the frame size:
The painting sizes of selected paintings are non-decreasing in display order:
The artistic values of selected paintings are non-decreasing in display order:
Find the maximum value of for which a valid arrangement exists.
Implementation Details
You need to implement the following function:
int32 max_paintings(int32 N, int32 M,int32[]A,int32[]B,int32[]S)
: the number of paintings
: the number of frames
: array of length , where is the size of painting
: array of length , where is the artistic value of painting
: array of length , where is the size of frame
The function should return the maximum number of paintings that can be displayed
数据范围与提示
Examples
The following call max_paintings(3, 3, [1, 2, 3], [1, 2, 4], [2, 3, 5]) should return 3
We have 3 paintings with sizes and artistic values .
We have 3 frames with sizes .
We can select all 3 paintings: painting 1 (size 1, value 1) in frame 1 (size 2), painting 2 (size 2, value 2) in frame 2 (size 3), and painting 3 (size 3, value 4) in frame 3 (size 5).
The sizes are non-decreasing: and the artistic values are non-decreasing: .
The following call max_paintings(4, 3, [1, 3, 2, 4], [3, 2, 3, 5], [3, 6, 4]) should return 3
We have 4 paintings with sizes and artistic values .
We have 3 frames with sizes .
We can select paintings with indices 1, 3, and 4: painting 1 (size 1, value 3) in frame 1 (size 3), painting 3 (size 2, value 3) in frame 3 (size 4), and painting 4 (size 4, value 5) in frame 2 (size 6).
The sizes are non-decreasing: and the artistic values are non-decreasing: .
The following call max_paintings(4, 3, [1, 3, 2, 4], [3, 2, 3, 5], [1, 1, 4]) should return 2
We have 4 paintings with sizes and artistic values .
We have 3 frames with sizes .
We can select painting 1 (size 1, value 3) in frame 1 or 2 (size 1), and painting 4 (size 4, value 5) in frame 3 (size 4).
The sizes are non-decreasing: and the artistic values are non-decreasing: .
Sample Grader
The sample grader reads the input in the following format:
Line 1: Two integers and
Line 2: integers (painting sizes)
Line 3: integers (artistic values)
Line 4: integers (frame sizes)
The sample grader calls max_paintings(N, M, A, B, S) and prints the returned value.
Note: The sample grader provided with this problem is just for testing your solution locally. The actual grader used during the contest may be different.
Constraints
for all valid indices
Scoring
Subtask 1 (10 points):
Subtask 2 (20 points): All frame sizes are larger than all painting sizes ( for all )
Subtask 3 (20 points): All artistic values are equal ( for all )
