Trung Bình Nhỏ Hơn

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie quản lý hai mảng $a$ và $b$ , mỗi mảng có $N$ phần tử ( $1 \leq N \leq 500$ , $1 \leq a_{i}, b_{i} \leq 10^{6}$ ).

Hãy đếm số cách chia cả hai mảng thành $k$ mảng con liên tiếp không rỗng ( $k$ bất kỳ, giống nhau cho cả hai) sao cho: với mọi $1 \leq i \leq k$ , trung bình cộng của mảng con thứ $i$ của mảng $a$ nhỏ hơn hoặc bằng trung bình cộng của mảng con thứ $i$ của mảng $b$ .

In kết quả modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng 1: Số nguyên $N$
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$
Dòng 3: $N$ số nguyên $b_{1}, b_{2}, \dots, b_{N}$

Dữ liệu ra

Một số nguyên -- số cách chia hợp lệ, modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 500$
$1 \leq a_{i}, b_{i} \leq 10^{6}$
Test 5-6: $N \leq 10$
Test 7-9: $N \leq 80$
Test 10-17: $N \leq 300$

Ví dụ

Input	Output	Giải thích
2 1 2 2 2	2	Cách 1: không chia ( $k = 1$ ), TB $a = 1.5 \leq 2.0 =$ TB $b$ . Cách 2: chia mỗi mảng thành 2 phần, $1 \leq 2$ và $2 \leq 2$ .
3 1 3 2 2 2 2	3	Ba cách chia hợp lệ: $k = 1$ (toàn bộ), $k = 2$ chia tại vị trí 1 hoặc 2, $k = 3$ không hợp lệ vì $3 > 2$ .
5 2 5 1 3 2 2 1 5 2 2	1	Chỉ có $k = 1$ là hợp lệ.

Bình luận

Không có bình luận tại thời điểm này.