Smaller Averages
플래티넘 I의견: 0
Bessie has two arrays of length \(N\) (\(1 \le N \le 500\)). The \(i\)-th element of
the first array is \(a_i\) (\(1 \le a_i \le 10^6\)) and the \(i\)-th element of the
second array is \(b_i\) (\(1 \le b_i \le 10^6\)).
Bessie wants to split both arrays into non-empty subarrays such that the
following is true.
- Every element belongs in exactly 1 subarray.
- Both arrays are split into the same number of subarrays. Let the number of subarrays the first and second array are split into be \(k\) (i.e. the first array is split into exactly \(k\) subarrays and the second array is split into exactly \(k\) subarrays).
- For all \(1 \le i \le k\), the average of the \(i\)-th subarray on the left of the first array is less than or equal to the average of the \(i\)-th subarray on the left of the second array.
Count how many ways she can split both arrays into non-empty subarrays while
satisfying the constraints modulo \(10^9+7\). Two ways are considered different if
the number of subarrays are different or if some element belongs in a different
subarray.
Problem credits: Alex Liang
SCORING
- Inputs 5-6: \(N \le 10\)
- Inputs 7-9: \(N \le 80\)
- Inputs 10-17: \(N \le 300\)
- Inputs 18-20: \(N \le 500\)
Problem credits: Alex Liang
The first line contains \(N\).
The next line contains \(a_1,a_2,...,a_N\).
The next line contains \(b_1,b_2,...,b_N\).
Output the number of ways she can split both arrays into non-empty subarrays
while satisfying the constraints modulo \(10^9+7\).
2
1 2
2 22The two valid ways are:
- Split the first array into \([1],[2]\) and the second array into \([2],[2]\).
- Split the first array into \([1,2]\) and the second array into \([2,2]\).
3
1 3 2
2 2 23The three valid ways are:
- Split the first array into \([1,3],[2]\) and the second array into \([2,2],[2]\).
- Split the first array into \([1,3],[2]\) and the second array into \([2],[2,2]\).
- Split the first array into \([1,3,2]\) and the second array into \([2,2,2]\).
5
2 5 1 3 2
2 1 5 2 21The only valid way is to split the first array into \([2],[5,1,3],[2]\) and the
second array into \([2],[1,5],[2,2]\).
7
3 5 2 3 4 4 1
5 3 5 3 3 4 1140평가 및 의견
Smaller Averages
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Smaller Averages