#2309

[중등부] 2024 KOI 2차대회 대비 모의고사 (3주차)

두 배열 나누기
서브태스크

2초 1024MB

문제

길이가 N인 두 개의 배열이 있다. 첫 번째 배열의 i번째 요소는 a_i이고, 두 번째 배열의 i번째 요소는 b_i다.

두 배열을 다음 조건을 만족하도록 비어 있지 않은 하위 배열들로 나누려고 한다:

모든 요소는 정확히 하나의 하위 배열에 포함된다.
두 배열이 동일한 수의 하위 배열로 나뉜다. 첫 번째 배열과 두 번째 배열이 모두 정확히 k개의 하위 배열로 나뉜다.
모든 1 \le i \le k에 대해, 첫 번째 배열의 i번째 하위 배열의 평균이 두 번째 배열의 i번째 하위 배열의 평균보다 작거나 같아야 한다.

이 조건을 만족하는 방법의 수를 10^9+7로 나눈 나머지로 출력하시오.

입력

첫 번째 줄에는 N이 주어진다. (1 \le N \le 500)

두 번째 줄에는 a_1, a_2, ..., a_N이 주어진다. (1 \le a_i \le 10^6)

세 번째 줄에는 b_1, b_2, ..., b_N이 주어진다. (1 \le b_i \le 10^6)

출력

첫 줄에 조건을 만족하는 방법의 수를 출력한다.

부분문제

번호	점수	조건
#1	10점	N \le 10
#2	20점	N \le 80
#3	30점	N \le 300
#4	40점	추가 제한 없음

예제 #1

2keyboard_return
2space_bar 4keyboard_return
4space_bar 4

해당 예제에서 가능한 두 가지 방법은:

첫 번째 배열을 [2],[4]로, 두 번째 배열을 [4],[4]로 나누는 경우
첫 번째 배열을 [2,4]로, 두 번째 배열을 [4,4]로 나누는 경우

예제 #2

3keyboard_return
3space_bar 9space_bar 6keyboard_return
6space_bar 6space_bar 6

해당 예제에서 가능한 세 가지 방법은:

첫 번째 배열을 [3,9],[6]로, 두 번째 배열을 [6,6],[6]로 나누는 경우

첫 번째 배열을 [3,9],[6]로, 두 번째 배열을 [6],[6,6]로 나누는 경우

첫 번째 배열을 [3,9,6]로, 두 번째 배열을 [6,6,6]로 나누는 경우

예제 #3

5keyboard_return
14space_bar 35space_bar 7space_bar 21space_bar 14keyboard_return
14space_bar 7space_bar 35space_bar 14space_bar 14

해당 예제에서 가능한 유일한 방법은:

첫 번째 배열을 [14],[35,7,21],[14]로, 두 번째 배열을 [14],[7,35],[14,14]로 나누는 경우

예제 #4

4keyboard_return
5space_bar 1space_bar 3space_bar 2keyboard_return
4space_bar 6space_bar 1space_bar 2

예제 #5

7keyboard_return
3space_bar 5space_bar 2space_bar 3space_bar 2space_bar 1space_bar 4keyboard_return
5space_bar 4space_bar 2space_bar 5space_bar 4space_bar 4space_bar 1