Bão

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
ldn694
Dạng bài
Điểm: 1600 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong một trò chơi, bản đồ đại đương được biểu diễn bằng một bảng ô vuông có kích thước \(𝑛 \times 𝑛\). Các dòng của bảng được đánh số từ \(1\) đến \(𝑛\), từ trên xuống dưới. Các cột của bảng được đánh số từ \(1\) đến \(𝑛\), từ trái sang phải. Ô nằm trên giao của dòng \(𝑖\) và cột \(𝑗\) của bảng gọi là ô \((𝑖,𝑗)\).

Ô \((𝑖,𝑗)\) chứa một số nguyên \(𝑟\) biểu diễn một cơn bão có bán kính là \(𝑟\), bão có tâm bão tại ô \((𝑖,𝑗)\); các ô \((𝑥, 𝑦)\) sẽ bị ảnh hưởng bởi bão tại ô \((𝑖,𝑗)\) khi \(|𝑥 − 𝑖| + |𝑦 − 𝑗| \leq 𝑟\) (khoảng cách Manhattan). Nếu \(𝑟 = 0\) thì tại ô đó không có bão.

Yêu cầu: Đếm số lượng ô không bị ảnh hưởng bão.

Input

  • Dòng đầu tiên gồm số nguyên dương \(𝑛\) \((𝑛 \leq 3000)\) mô tả kích thước của bảng;
  • \(𝑛\) dòng tiếp theo, mỗi dòng gồm \(𝑛\) số nguyên \(𝑟\) \((0 \leq 𝑟 \leq 𝑛)\) mô tả các cơn bão.

Output

  • Một số duy nhất là số lượng ô không bị ảnh hưởng bão.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(𝑛 \leq 100\);
  • Subtask \(2\) (\(20\%\) số điểm): \(𝑟 \leq 20\);
  • Subtask \(3\) (\(20\%\) số điểm): Các ô có bão đều có bán kính bằng nhau;
  • Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
4
0 0 0 0
0 0 0 0
0 0 2 0
0 0 0 0
Output 
5
Note

Những ô được gạch chân là những ô bị ảnh hưởng bởi bão.

Bình luận