VOSLIS - Dãy con chung
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho 2 dãy a[1..N] và b[1..M]. Gọi c[1..k] là 1 dãy con chung (không cần liên tiếp) bất kì của 2 dãy này. Đặt f(c) = abs(c[2] - c[1]) + abs(c[3] - c[2]) + .. + abs(c[k] - c[k - 1]). Nếu số phần tử của c < 2 thì f(c) = 0.
Xác định dãy con chung có giá trị f lớn nhất và in ra giá trị đó.
Input
- Dòng 1: 2 số nguyên N và M
- Dòng 2: N số nguyên biểu diễn dãy A
- Dòng 3: M số nguyên biểu diễn dãy B
Output
Một dòng duy nhất ghi số nguyên kết quả.
Giới hạn:
- 20% số test có 1 <= N, M <= 20
- 40% số test có 1 <= N, M <= 200
- 60% số test có 1 <= N, M <= 2000
Trong tất cả các test 1<= N, M <= 5000
Trong tất cả các test -10^9 <= a[i], b[i] <= 10^9
Example
Input: 4 4 1 15 8 7 15 1 7 8 Output: 8
Giải thích:
Dãy 15 7
- Người up: theguiler
- Nguồn bài: VOS Round 30 - Liên