Ô giao tối ưu giữa hàng và cột

Bối cảnh

Một trung tâm điều phối đặt một nút quan sát tại ô (i,j) của ma trận. Khi chọn nút này, toàn bộ dữ liệu trên hàng i và cột j được đưa vào một gói phân tích chung. Ô giao (i,j) nằm trên cả hàng và cột nên chỉ được tính một lần. Giá trị của lựa chọn vì vậy là:

score(i,j) = sumRow[i] + sumCol[j] - a[i][j].

Hãy tìm ô có score lớn nhất. Nếu có nhiều ô cùng score, chọn hàng nhỏ hơn; nếu vẫn bằng nhau, chọn cột nhỏ hơn.

Bài Medium này yêu cầu tách ma trận thành hai loại thông tin tiền xử lý khác nhau: tổng từng hàng và tổng từng cột. Sau đó mỗi ô được đánh giá trong O(1), thay vì mỗi lần lại duyệt nguyên hàng và cột.

Điểm tư duy là nhận ra phần giao bị đếm hai lần và phải trừ đúng một lần.

Yêu cầu

1. Trong lúc đọc ma trận, tính rowSum[i] và colSum[j].
2. Duyệt mọi ô, tính rowSum[i]+colSum[j]-a[i][j].
3. Cập nhật best; duyệt row-major tự xử lý tie.

Input

Dòng 1: rows cols; sau đó ma trận.

Output

Một dòng maxScore row col.

Ràng buộc

1 ≤ rows,cols ≤ 100, |a[i][j]| ≤ 10^9.

Ví dụ 1

Input

3 3
1 2 3
4 5 6
7 8 9

Output

33 2 2

Giải thích

Tổng các hàng là 6,15,24; tổng các cột là 12,15,18. Với ô (2,2) có giá trị 9, score hợp của hàng 2 và cột 2 là 24+18-9 = 33; trừ 9 một lần vì ô giao đã được tính ở cả row sum lẫn column sum. Kiểm tra các ô còn lại cho score nhỏ hơn 33, nên đáp án là 33 2 2.

Ví dụ 2

Input

1 4
5 1 2 3

Output

11 0 0

Giải thích

Ma trận chỉ có một hàng, tổng hàng là 5+1+2+3 = 11. Ở bất kỳ cột j nào, công thức rowSum + colSum[j] - a[0][j] đều bằng 11 + a[0][j] - a[0][j] = 11. Tất cả ô cùng score nên quy tắc lấy ứng viên xuất hiện đầu tiên chọn (0,0), cho 11 0 0.

Thông tin học tập

• Module: M03
• Buổi: B11
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: 2D static arrays, row sums, column sums, combined score, optimization, tie-break
• Giới hạn kiến thức: B01-B11
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100