Vành có tổng lớn nhất

Bối cảnh

Một ma trận vuông được xem như nhiều "vành" đồng tâm. Vành 0 là toàn bộ biên ngoài; sau khi bỏ biên ngoài, biên của phần còn lại là vành 1; cứ tiếp tục như vậy cho tới tâm. Với n lẻ, vành cuối cùng chỉ có một ô trung tâm. Với n chẵn, vành trong cùng vẫn là một khung 2×2.

Hệ thống cần tìm vành có tổng giá trị lớn nhất. Nếu nhiều vành có cùng tổng, chọn chỉ số vành nhỏ hơn (gần biên ngoài hơn). Bạn phải tính mỗi ô của một vành đúng một lần, đặc biệt chú ý không cộng trùng bốn góc. Bài Medium này nâng thao tác "tổng phần bên trong" thành việc phân rã toàn ma trận theo lớp hình học và xử lý cả trường hợp lớp co lại thành một hàng/cột.

Khó khăn là xác định bốn cạnh của từng layer và tránh double-count ở góc.

Yêu cầu

1. Vành k có top=left=k, bottom=right=n-1-k.
2. Nếu chỉ còn một ô/hàng, cộng đúng một lần.
3. Nếu là khung thực sự, cộng cạnh trên, phải, dưới, trái với phạm vi loại góc đã tính.
4. Cập nhật tổng lớn nhất.

Input

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

Output

Một dòng layerIndex maxSum.

Ràng buộc

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

Ví dụ 1

Input

5
1 1 1 1 1
1 2 2 2 1
1 2 9 2 1
1 2 2 2 1
1 1 1 1 1

Output

0 16

Giải thích

Ma trận 5×5 có ba vành. Vành 0 là biên ngoài gồm 16 ô đều bằng 1 nên tổng bằng 16. Vành 1 là biên của khối 3×3 bên trong, gồm 8 ô đều bằng 2 nên cũng tổng 16; vành 2 chỉ là ô tâm 9 nên tổng 9. Giá trị lớn nhất là 16 và xuất hiện ở cả vành 0 lẫn vành 1; vì thuật toán chỉ cập nhật khi tổng lớn hơn, tie được giữ ở vành xuất hiện trước là 0. Vì vậy output là 0 16.

Ví dụ 2

Input

1
7

Output

0 7

Giải thích

Với n=1 chỉ tồn tại đúng một vành, chính là ô (0,0) có giá trị 7. Tổng của vành 0 bằng 7 và không có phương án khác. Kết quả trực tiếp là 0 7.

Thông tin học tập

• Module: M03
• Buổi: B12
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: 2D static arrays, concentric layers, border traversal, optimization, edge handling
• Giới hạn kiến thức: B01-B12
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100