1. Tóm tắt đề bài

Cho ma trận kích thước ~N \times M~. Tính tổng các phần tử nằm trên 4 đường biên của ma trận (dòng đầu, dòng cuối, cột đầu, cột cuối). Mỗi phần tử ở 4 góc chỉ được tính đúng một lần.

• Dữ liệu vào (Input):
  • Dòng 1: Hai số nguyên ~N, M~ (~1 \le N, M \le 1000~).
  • ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số nguyên ~A_{i, j}~ (~-10^6 \le A_{i, j} \le 10^6~).
• Dữ liệu ra (Output):
  • Một số nguyên duy nhất là tổng các phần tử nằm trên biên của ma trận.

2. Phân tích bài toán & Giới hạn

• Giới hạn kích thước: ~N, M \le 1000~.

  • Tổng số phần tử của ma trận tối đa là ~1000 \times 1000 = 10^6~.
  • Số lượng phần tử nằm trên biên tối đa là ~2 \times (N + M) - 4 \approx 4000~ phần tử (với ~N, M > 1~).
  • Kích thước này rất nhỏ, thời gian đọc và tính toán diễn ra tức thì (~< 0.05~ giây).

• Lưu ý kiểu dữ liệu (Tránh tràn số):

  • Các giá trị ~A_{i, j} \in [-10^6, 10^6]~.
  • Tổng trên biên có thể đạt tới ~\approx 4000 \times 10^6 = 4 \times 10^9~, vượt quá giới hạn của số nguyên có dấu 32-bit (int). Bắt buộc dùng kiểu dữ liệu 64-bit (long long trong C++) cho biến lưu tổng.

3. Thuật toán xử lý

• Ý tưởng:

  1. Một ô tọa độ ~(i, j)~ (với ~1 \le i \le N~ và ~1 \le j \le M~) thuộc đường biên khi và chỉ khi thỏa mãn ít nhất một trong các điều kiện sau:
     • Nằm ở dòng đầu: ~i = 1~
     • Nằm ở dòng cuối: ~i = N~
     • Nằm ở cột đầu: ~j = 1~
     • Nằm ở cột cuối: ~j = M~
  2. Khởi tạo biến lưu tổng ans = 0 (kiểu dữ liệu 64-bit).
  3. Khi đọc dữ liệu từ luồng vào theo từng hàng ~i~ từ ~1~ đến ~N~ và từng cột ~j~ từ ~1~ đến ~M~:
     • Nếu ~(i == 1 \text{ hoặc } i == N \text{ hoặc } j == 1 \text{ hoặc } j == M)~ thì cộng trực tiếp giá trị ô đó vào ans.
     • Cách làm này giúp tính toán trực tiếp ngay khi nhập, không cần lưu trữ ma trận vào bộ nhớ và tự động tránh việc cộng lặp lại các ô ở góc.
  4. In ra giá trị ans.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(N \times M)~ — Đọc và kiểm tra mỗi ô đúng 1 lần, thực thi cực nhanh trong thời gian ~< 0.05~ giây.
  • Không gian (bộ nhớ): ~\mathcal{O}(1)~ nếu cộng dồn trực tiếp khi đọc, hoặc ~\mathcal{O}(N \times M)~ nếu lưu toàn bộ ma trận (với ~10^6~ số nguyên chỉ tốn khoảng ~4\text{ MB}~, hoàn toàn tối ưu).