Chirox đi sửa hàng rào

View as PDF

Submit solution

Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 500M
Input: stdin
Output: stdout

Authors:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Sau khi trở nên túng quẫn vì mua skin game, Chirox phải về quê chăn rau và nuôi gà. Nhưng cuộc đời Chirox có mấy khi được suôn sẻ, những tên trộm luôn nhòm ngó khu vườn nhà Chirox. Sau nhiều lần bị trộm, Chirox quyết định phải sửa lại hàng rào cho cao lên để những tên trộm chân ngắn không thể trèo vào được.

Kế hoạch của Chirox như sau: Chirox sẽ chở một chồng gỗ và lần lượt đi qua từng thanh hàng rào từ trái qua phải, sau đó nếu cảm thấy thanh hàng rào này cần phải được sửa cho cao lên, Chirox sẽ lấy một miếng gỗ mới phù hợp trong chồng gỗ để bổ sung cho thanh hàng rào đó. Chiều cao của thanh rào sau khi được sửa sẽ bằng chiều cao thanh rào ban đầu cộng cho chiều dài của miếng gỗ mới. Tuy nhiên, vì là một người lười biếng, sau khi đã chọn 1 miếng gỗ phù hợp cho thanh hàng rào đó thì những miếng gỗ ở bên trên sẽ bị Chirox quăng đi (vì lười xếp lại). Lười biếng là vậy, Chirox vẫn muốn hàng rào của mình được sửa một cách tốt nhất.

Gọi độ cao của hàng rào là chiều cao của thanh rào thấp nhất trong hàng rào. Bạn hãy giúp Chirox lười biếng sửa hàng rào một cách lười biếng nhưng vẫn sửa được cho độ cao hàng rào là lớn nhất có thể.

*Input: *

  • Dòng đầu tiên chứa số nguyên dương n là số thanh rào trong hàng rào của Chirox
  • Dòng thứ hai chứa n số nguyên dương ai(in), tương ứng là chiều cao ban đầu của thanh rào thứ i
  • Dòng thứ ba chứa số nguyên dương m là số ván gỗ trong chồng gỗ của Chirox
  • Dòng thứ tư chứa m số nguyên dương b1,b1,...,bm lần lượt là chiều dài của các ván gỗ trong chồng gỗ từ trên xuống dưới

*Output: * Một dòng duy nhất chứa một số nguyên là độ cao hàng rào lớn nhất mà Chirox có thể sửa được bằng cách sửa lười biếng ấy

Giới hạn:

  • 1n,m5.105
  • 1a[i]108,b[i]108

Ví dụ:

Input
Copy
6
2 5 4 1 7 5
7
2 3 1 3 2 4 6
Output
Copy
5

*Giải thích: * Một cách sửa thỏa mãn:

  • Sửa thanh rào thứ 1 bằng ván gỗ thứ 2, chiều cao mới của thanh rào là 2+3=5
  • Sửa thanh rào thứ 3 bằng ván gỗ thứ 4, chiều cao mới của thanh rào là 4+3=7
  • Sửa thanh rào thứ 4 bằng ván gỗ thứ 7, chiều cao mới của thanh rào là 1+6=7
  • Vậy chiều cao của các thanh rào sau cùng là: 5,5,7,7,7,5=>5 là chiều cao của thanh rào thấp nhất => 5 là độ cao của hàng rào và là lớn nhất có thể đạt được

Comments

Please read the guidelines before commenting.



  • -2
    anhtuan2007  commented 6:05:10 am, 29/11/2022

    my time has come


  • 2
    nganngan2710  commented 4:14:42 am, 22/11/2021

    Đã update test!