Dãy Mới
Xem PDF
Điểm:
1000 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
cho hai dãy có cùng \(n\) số nguyên dương \(a_1,a_2,...,a_n\) và \(b_1,b_2,...,b_n\).
muốn tạo ra một dãy cũng có \(n\) số nguyên dương \(c_1,c_2,...,c_n\) thỏa mãn rằng \(c_k\) \((1 \le k \le n)\) là giá trị lớn nhất của \(a_i \times b_j\) với mọi \(1 \le i \le j \le k\). Hay nói một cách khác, cần tạo ra một dãy thỏa mãn rằng \(c_k = max(a_i \times b_j)\) với mọi \((1 \le i \le j \le k)\).
Yêu cầu: Bạn hãy giúp tạo và in ra dãy \(c\) thỏa mãn điều kiện trên.
Input
- Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 10^6)\).
- Dòng tiếp theo chứa dãy \(a_1,a_2,...,a_n\) \((1 \le a_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.
- Dòng cuối cùng chứa dãy \(b_1,b_2,...,b_n\) \((1 \le b_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.
Output
- Gồm \(n\) dòng, dòng thứ \(i\) \((1 \le i \le n)\) in ra số \(c_i\) thỏa mãn điều kiện (\(i\) theo thứ tự tăng dần \(1,2,...,n\)).
Scoring
- Subtask \(1\) (\(30\%\) số điểm): Có \(n \le 100\).
- Subtask \(2\) (\(30\%\) số điểm): Có \(n \le 2 \times 10^5\).
- Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
3
3 2 20
1 4 1
Output
3
12
20Note
- \(c_1 = max(a_1 \times b_1) = 3\).
- \(c_2 = max(a_1 \times b_1,a_1 \times b_2,a_2 \times b_2) = 12\).
- \(c_3 = max(a_1 \times b_1,a_1 \times b_2,a_1 \times b_3,a_2 \times b_2,a_2 \times b_3,a_3 \times b_3) = 20\).
Bình luận
trời ơi fix đi chứ dpt O(n) mà TLE là sao???
-
4
shiba
12:52 a.m. 31 Tháng 5, 2023
-
0
dbthuan208
9:02 a.m. 31 Tháng 5, 2023
1 bình luận nữaông mới là người đi fix. Đpt O(n) nhưng phải cout ra nhiều nên nó cũng mất nhiều time. Bạn thay endl thành "\n" là AC nhé!
ô sờ kê cảm ơn ông