trang chủ / bài tập / xepgach1

Xếp gạch

Đề bài

Mô tả

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à a1,a2,…,an.

An cần thực hiện m lượt chơi tương ứng với dãy số nguyên dương b1,b2,…,bm đã biết trước. Ở lượt thứ i (1≤i≤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ị bi.
  • Xếp thêm bi viên gạch lên chồng gạch thứ j (1≤j≤n) nếu tất cả các chồng gạch thứ j,j+1,j+2,…,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 a1,a2,…,an (ai≤108) mô tả số gạch ở các chồng ban đầu.
  • Dòng 3: ghi m số nguyên dương b1,b2,…,bm (bi≤108) mô tả các giá trị mà ban tổ chức đưa trước cho An, bi 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≤n≤103.
  • 30% số test tương ứng 30% số điểm thỏa mãn m=2 và 103<n≤104.
  • 30% số test tương ứng 30% số điểm thỏa mãn 104<n,m≤106.

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0