[USACO24OPEN] Smaller Averages G

Luogu

IDLGP10282

Time2000ms

Memory256MB

DifficultyP5

动态规划 DPUSACO2024前缀和双指针 two-pointer

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. 1. Every element belongs in exactly 1 subarray. 2. 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). 3. 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. ## Input 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 Output the number of ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo $10^9+7$. [samples] ## Note ##### For Sample 1: The two valid ways are: 1. Split the first array into $[1],[2]$ and the second array into $[2],[2]$. 2. Split the first array into $[1,2]$ and the second array into $[2,2]$. ##### For Sample 2: The three valid ways are: 1. Split the first array into $[1,3],[2]$ and the second array into $[2,2],[2]$. 2. Split the first array into $[1,3],[2]$ and the second array into $[2],[2,2]$. 3. Split the first array into $[1,3,2]$ and the second array into $[2,2,2]$. ##### For Sample 3: The 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]$. #### 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$

Samples

Input #1

2
1 2
2 2

Output #1

Input #2

3
1 3 2
2 2 2

Output #2

Input #3

5
2 5 1 3 2
2 1 5 2 2

Output #3

Input #4

7
3 5 2 3 4 4 1
5 3 5 3 3 4 1

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[USACO24OPEN] Smaller Averages G",
    "description": {
      "content": "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$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10282"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments