Subtask 1: \(r,c \leq 50\)

Với \(r,c\) nhỏ, ta có thể brute-force như yêu cầu đề bài. Với mỗi ô (\(x, y\)), ta duyệt qua toàn bộ \(r\times c\) ô để tìm các ô \(1\). Sau đó sắp xếp để tìm \(k\) ô có khoảng cách gần nhất rồi cộng vào kết quả.

ĐPT: \(O(r^2\times c^2\times log_2(r\times c))\)

Subtask 2: \(r,c \leq 300, k = 1\)

Với \(k = 1\), bài toán chuyển thành với mỗi ô tìm ô \(1\) gần nhất. Ta có thể áp dụng tìm kiếm nhị phân để tìm khoảng cách gần nhất. Giả sử ta cần kiểm tra trong "bán kính" \(dist\) của ô \((x,y)\) có tồn tại ô \(1\) nào hay không, ta có nhận xét tập các ô có khoảng cách không quá \(dist\) đến ô (\(x, y\)) sẽ có dạng một hình thoi. Để tính tổng của hình thoi này, ta có thể tính theo từng hàng một, và tính nhanh tổng của từng hàng bằng tổng tiền tố.

ĐPT: \(O(r\times c \times (r + c) \times log_2(r + c))\)

Subtask \(4\) (\(20\%\) số điểm): \(r, c \leq 1000\)

Với mỗi vị trí \((i, j)\), gọi \(d(i, j)\) khoảng cách của thằng gần thứ \(k\) đến ô \((i, j)\), ta có thể thực hiện tìm kiếm nhị phân giá trị này, với giá trị \(x\) ta cần kiểm tra xem có bao nhiêu thằng có khoảng cách bé hơn hoặc bằng \(x\) tới ô \((i, j)\). Ta sử dụng kỹ thuật xoay bảng một góc \(45^{o}\) và tổng cộng dồn để đếm số lượng này.

Ta cần tính tổng khoảng cách của \(k\) ô gần ô \((i, j)\) nhất, ta có thể chia ra 2 phần là tính tổng khoảng cách các ô \((x, y)\) mà \(|x - i| + |y - j| < d(i, j)\) và tính số ô có khoảng cách bằng \(d(i, j)\) rồi nhân vào.

Để tính tổng khoảng cách các ô \((x, y)\) mà \(|x - i| + |y - j| < d(i, j)\) ta sử dụng mảng cộng dồn tam giác và chia trường hợp để phá dấu trị tuyệt đối.

Subtask 5: \(k = 1\)

Ta có thể sử dụng BFS để tìm ô gần nhất. Ban đầu ta sẽ đẩy vào hàng đợi các ô \(1\), sau đó thực hiện BFS như bình thường.

ĐPT: \(O(r \times c)\)

Subtask \(6\) (\(20\%\) số điểm): \(r, c \leq 2000\)

Nhận xét : \(d(i, j) \leq d(i, j - 1) + 1\) nên ta có thể lấy kết quả \(d(i, j - 1)\) rồi giảm dần đến khi tìm được \(d(i, j)\)