Subtask ~1~:

• Đặt sức mạnh ban đầu là ~res = 0~, sức mạnh hiện tại là ~s = 0~.

• Ta cứ đi dần từ ô ~(1,1)~ tới ô ~(1,m)~, nếu sức mạnh hiện tại không đủ để đánh bại con quái vật ở ô ~(1,i)~ đang xét, ta cộng thêm lượng ~h_{1,i} - s + 1~ vào kết quả và sức mạnh hiện tại.

Đáp án là ~res~.

Subtask ~2~:

Ta sẽ đi thử từng sức mạnh ban đầu, lưu ý rằng chỉ kiếm tra những sức mạnh lớn hơn hẳn giá trị của ô ~(1,1)~.

Giả sử ta đang kiểm tra xem ~s~ có phải kết quả không, ta có thể quy hoạch động như sau:

• Đặt ~dp_{i,j}~ là sức mạnh nhiều nhất hiện có nếu đi từ ô ~(1,1)~ tới ô ~(i,j)~. Đầu tiên khởi tạo ~dp_{i,j} = -\infty~, ~dp_{1,1} = s + h_{1,1}~
• Đặt ~val = max (dp_{i-1,j}, dp_{i,j-1})~. Nếu ~val > h_{i,j}~ thì cập nhật ~dp_{i,j} = val + h_{i,j}~.
• Nếu ~dp(n,m) \neq -\infty~ thì ~s~ thỏa mãn.

Subtask ~3~:

• Cách ~1~: Ta nhận thấy rằng có thể chặt nhị phân kết quả, sau đó làm tương tự subtask ~2~ để kiểm tra. Độ phức tạp: ~O(n*m*log)~ \end{itemize}
• Cách ~2~: Ta làm ngược từ cuối về, đặt ~dp_{i,j}~ là sức mạnh hiện tại nhỏ nhất để đi từ ô ~(i,j)~ tới ô ~(n,m)~.
• ~dp_{i,j} = min(max (dp_{i+1,j}-h_{i,j}, h_{i,j} + 1), max (dp_{i,j+1} - h_{i,j},h_{i,j}+1))~ Kết quả là ~dp_{1,1}~. Độ phức tạp: ~O(n*m)~