Xếp gạch

Điểm: 3,00 (OI)

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

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

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Sau khi tham gia trò chơi "Bốc số", An tiếp tục tham gia trò chơi "Xếp gạch". Ban tổ chức cho trước $n$ chồng gạch được xếp thành một hàng ngang và đánh số từ $1$ đến $n$ . Số viên gạch ở các chồng lần lượt là $a_{1}, a_{2}, \dots, a_{n}$ .

An cần thực hiện $m$ lượt chơi tương ứng với dãy số nguyên dương $b_{1}, b_{2}, \dots, b_{m}$ đã biết trước. Ở lượt thứ $i$ ( $1 \leq i \leq m$ ), An được quyền thực hiện chỉ một trong hai lựa chọn:

Bỏ qua không sử dụng giá trị $b_{i}$ .
Xếp thêm $b_{i}$ viên gạch lên chồng gạch thứ $j$ ( $1 \leq j \leq n$ ) nếu tất cả các chồng gạch thứ $j, j + 1, j + 2, \dots, n$ chưa từng được xếp thêm viên gạch nào trong các lượt trước đó.

Trò chơi dừng lại khi hết lượt hoặc An đã thực hiện xếp thêm gạch ở chồng thứ $n$ . Khi đó ban tổ chức sẽ đếm số gạch ở mỗi chồng và lấy số gạch ở chồng ít nhất làm điểm số của An.

Cách chơi của An là tối ưu nhất nên cậu đã đạt được số điểm tối đa của trò chơi.

Yêu cầu: Hãy tìm ra số điểm An đạt được.

Dữ liệu vào

Dòng $1$ : ghi hai số nguyên dương $n$ và $m$ lần lượt là số chồng gạch ban đầu và số lượt chơi của An.
Dòng $2$ : ghi $n$ số nguyên không âm $a_{1}, a_{2}, \dots, a_{n}$ ( $a_{i} \leq 10^{8}$ ) mô tả số gạch ở các chồng ban đầu.
Dòng $3$ : ghi $m$ số nguyên dương $b_{1}, b_{2}, \dots, b_{m}$ ( $b_{i} \leq 10^{8}$ ) mô tả các giá trị mà ban tổ chức đưa trước cho An, $b_{i}$ là giá trị được sử dụng ở lượt thứ $i$ .

Dữ liệu ra

Ghi $1$ dòng chứa số điểm An đạt được.

Ràng buộc

$40 %$ số test tương ứng $40 %$ số điểm thỏa mãn $m = 1, 1 \leq n \leq 10^{3}$ .
$30 %$ số test tương ứng $30 %$ số điểm thỏa mãn $m = 2$ và $10^{3} < n \leq 10^{4}$ .
$30 %$ số test tương ứng $30 %$ số điểm thỏa mãn $10^{4} < n, m \leq 10^{6}$ .

Ví dụ

Input	Output	Giải thích
5 3 2 5 1 4 6 1 3 4	4	An bỏ qua lượt $1$ ; An xếp $3$ viên gạch vào chồng gạch thứ nhất ở lượt $2$ ; An xếp $4$ viên gạch vào chồng gạch thứ ba ở lượt $3$ . Khi đó số gạch ở các chồng gạch lần lượt là $5; 5; 5; 4; 6$ nên số điểm đạt được là $4$ .

Bình luận

quani16khang_dd

đã bình luận lúc 15, Tháng 4, 2026, 14:59

who ask?

Thái Minh Tâm

đã bình luận lúc 26, Tháng 3, 2026, 8:58

i gonna to be die