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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0