JOI 2025 - Bitaro the Brave 2

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Dũng sĩ Bitaro lên đường phiêu lưu để đánh bại các quái vật.

Bitaro có một giá trị gọi là sức mạnh, với giá trị ban đầu là \(x\). Có \(N\) quái vật, được đánh số từ \(1\) đến \(N\). Để đánh bại quái vật \(i\) (\(1 \le i \le N\)), sức mạnh của Bitaro phải ít nhất là \(A_i\). Sau khi đánh bại quái vật này, sức mạnh của Bitaro tăng thêm \(B_i\).

Bitaro muốn đánh bại tất cả quái vật theo cách sau:

  1. Chọn một quái vật \(j\) (\(1 \le j \le N\)) làm điểm bắt đầu, rồi lần lượt đánh bại các quái vật \(j,j+1,\ldots,N\) theo đúng thứ tự này.
  2. Sau đó, nếu \(j \ge 2\), lần lượt đánh bại các quái vật \(1,2,\ldots,j-1\) theo đúng thứ tự này.

Cho thông tin về các quái vật, hãy tìm giá trị sức mạnh ban đầu \(x\) nhỏ nhất để Bitaro có thể đánh bại tất cả quái vật.

Dữ liệu vào

Dữ liệu vào có dạng:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Dữ liệu ra

In ra một dòng chứa một số nguyên là giá trị sức mạnh ban đầu \(x\) nhỏ nhất để Bitaro có thể đánh bại tất cả quái vật.

Ràng buộc

  • \(2 \le N \le 500\,000\).
  • \(0 \le A_i \le 10^9\) (\(1 \le i \le N\)).
  • \(0 \le B_i \le 10^9\) (\(1 \le i \le N\)).
  • Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

  1. 10 điểm: \(N \le 2\,000\) và giá trị sức mạnh ban đầu nhỏ nhất cần có không quá \(10\).
  2. 21 điểm: \(N \le 2\,000\).
  3. 19 điểm: Giá trị sức mạnh ban đầu nhỏ nhất cần có không quá \(10\).
  4. 22 điểm: \(B_i=1\) (\(1 \le i \le N\)).
  5. 28 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
5
1 3 2 8 6
4 3 1 1 2
Output 
1
Giải thích

Với sức mạnh ban đầu bằng \(1\), Bitaro có thể đánh bại tất cả quái vật theo thứ tự sau:

  1. Đánh bại quái vật \(1\). Sức mạnh tăng thêm \(4\), trở thành \(5\).
  2. Đánh bại quái vật \(2\). Sức mạnh tăng thêm \(3\), trở thành \(8\).
  3. Đánh bại quái vật \(3\). Sức mạnh tăng thêm \(1\), trở thành \(9\).
  4. Đánh bại quái vật \(4\). Sức mạnh tăng thêm \(1\), trở thành \(10\).
  5. Đánh bại quái vật \(5\). Sức mạnh tăng thêm \(2\), trở thành \(12\).

Không có cách nào đánh bại tất cả quái vật khi sức mạnh ban đầu không quá \(0\), nên đáp án là \(1\).

Ví dụ này thỏa mãn ràng buộc của các subtasks \(1,2,3,5\).

Ví dụ 2

Input 
5
1 6 3 3 2
1 2 1 0 1
Output 
3
Giải thích

Với sức mạnh ban đầu bằng \(3\), Bitaro có thể đánh bại tất cả quái vật theo thứ tự sau:

  1. Đánh bại quái vật \(3\). Sức mạnh tăng thêm \(1\), trở thành \(4\).
  2. Đánh bại quái vật \(4\). Sức mạnh tăng thêm \(0\), vẫn bằng \(4\).
  3. Đánh bại quái vật \(5\). Sức mạnh tăng thêm \(1\), trở thành \(5\).
  4. Đánh bại quái vật \(1\). Sức mạnh tăng thêm \(1\), trở thành \(6\).
  5. Đánh bại quái vật \(2\). Sức mạnh tăng thêm \(2\), trở thành \(8\).

Không có cách nào đánh bại tất cả quái vật khi sức mạnh ban đầu không quá \(2\), nên đáp án là \(3\).

Ví dụ này thỏa mãn ràng buộc của các subtasks \(1,2,3,5\).

Ví dụ 3

Input 
10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1
Output 
9
Giải thích

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Ví dụ 4

Input 
7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580
Output 
0
Giải thích

Ví dụ này thỏa mãn ràng buộc của các subtasks \(1,2,3,5\).

Nguồn

Đề bài Bitaro the Brave 2, JOI 2024/2025, vòng chung kết quốc gia, bài 2 (tiếng Nhật) của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: