DÃY CON CHUNG

View as PDF

Submit solution

All submissions

Best submissions

Points: 200.00 (partial)

Time limit: 1.0s

Memory limit: 1G

Input: stdin

Output: stdout

Author:

kieulqd

Problem type

Allowed languages

C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Cho 2 dãy $A$ và $B$ , mỗi dãy có $N$ phần tử. Hãy tìm số lượng dãy con chung (không cần phải liên tiếp) của 2 dãy A và B sao cho tích các phần tử trong dãy con chung là lớn nhất. Hai dãy $p$ và $q$ được gọi là giống nhau khi có cùng độ dài, mọi $i$ thoả mãn $p_{i} = q_{i}$ và được lấy tại cùng 1 vị trí cùng 1 dãy A hoặc B

Input

Dòng 1: Số nguyên dương $N (N \leq 10^{3})$
Dòng 2: Gồm N số nguyên $A_{i} (1 \leq A_{i} \leq 1000)$
Dòng 3: Gồm N số nguyên $B_{i} (1 \leq B_{i} \leq 1000)$

Output: Gồm 1 số nguyên H duy nhất là số lượng dãy con thỏa mãn yều cầu đề bài. Vì kết quả có thể rất lớn nên hãy in ra kết quả sau khi chia dư cho $10^{9} + 7$ .

Ví dụ

INPUT

Copy

6
5 6 3 2 8 1
5 3 6 8 2 8

OUTPUT

Copy

Subtask

Subtask 1: $N \leq 10; A_{i}, B_{i} \leq 9$
Subtask 2: $N \leq 20; A_{i}, B_{i} \leq 100$
Subtask 3: $N \leq 1000; A_{i}, B_{i} \leq 1000$

Comments

Please read the guidelines before commenting.

2

huynhchiton981 commented 12:49:12 pm, 28/02/2023

bai nay test sai co oi : (