4902.cpp

#include <stdio.h>

// 1: 1
// 2: 4 (+3)
// 3: 9 (+5)
// 4: 16 (+7)

int n;
int arr[405][900];
int sum[405][900];
int D[405][900]; // 정방향


int main()
{
	for (int test = 1; ; test++) {
		int dap = -400 * 800 * 1000;
		
		scanf("%d", &n);
		if (n == 0) return 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i * 2 - 1; j ++) {
				scanf("%d", &arr[i][j]);
				sum[i][j] = sum[i][j - 1] + arr[i][j];
				if (dap < arr[i][j]) dap = arr[i][j]; // 크기가 1인 경우
				
				D[i][j] = arr[i][j];
			}
		}

		for (int sz = 2; sz <= n; sz++) { // 정방향
			for (int sx = 1; sx + sz - 1 <= n; sx++) {
				for (int sy = 1; sy <= sx * 2 - 1; sy += 2) {
					// (sx, sy)
					D[sx][sy] = D[sx][sy] + (sum[sx+sz - 1][sy + (sz-1) * 2] - sum[sx+sz-1][sy - 1]);
					if (dap < D[sx][sy]) dap = D[sx][sy];
					// printf("(%d, %d); sz = %d => %d\n", sx, sy, sz, c);
				}
			}
		}

		for (int sz = 2; sz <= n; sz++) { // 역방향
			for (int sx = n; sx - sz + 1>= 1; sx--) {
				for (int sy = sz * 2; sy <= (sx - sz + 1) * 2 - 1 ; sy += 2) {
					D[sx][sy] = D[sx][sy] + (sum[sx - sz + 1][sy] - sum[sx - sz + 1][sy - (sz - 1) * 2 - 1]);
					if (dap < D[sx][sy]) dap = D[sx][sy]; 
					// printf("(%d, %d); sz = %d => %d\n", sx, sy, sz, c);
				}
			}
		}

		printf("%d. %d\n", test, dap);
	}

	return 0;
}