Submission #9482

#	Time	Username	Problem	Language	Result	Execution time	Memory
9482		sior	On grid (kriii2_O)	C++98	0 / 4	0 ms	2384 KiB

O

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <utility>

using namespace std;

#define INF 987654
int cache[301][301];
int board[301][301];
int numOfX, numOfY;

int gridSum(int y1, int x1, int y2, int x2);
int generate(int y_here, int x_here/*현재 위치*/);



int main()
{

	cin >> numOfX >> numOfY;

	memset(cache, -1, sizeof(cache));

	for (int y = 0; y < numOfY; y++)
	{
		for (int x = 0; x < numOfX; x++)
		{
			cin >> board[y][x];
		}
	}

	for (int x = 1; x < numOfX; x++)
	{
		board[0][x] += board[0][x - 1];
	}
	for (int y = 1; y < numOfY; y++)
	{
		board[y][0] += board[y - 1][0];
		for (int x = 1; x < numOfX; x++)
		{
			board[y][x] += board[y][x - 1] + board[y - 1][x];
			board[y][x] -= board[y - 1][x - 1];
		}
	}

	cout << generate(0, 0) << endl;
	return 0;
}


int generate(int y_here, int x_here/*현재 위치*/)//현재 위치에서의 최대 값을 반환
{

	if (y_here >= (numOfY) && x_here != (numOfX)) return -INF;
	if (y_here != (numOfY) && x_here >= (numOfX)) return -INF;

	int &ret = cache[y_here][x_here];

	if (ret != -1) return ret;

	ret = 0;


	for (int y = y_here; y < numOfY; y++)
	{
		for (int x = x_here; x < numOfX; x++)
		{
			if (y + 1 <= numOfY && x + 1 <= numOfX)
			{
				int a = gridSum(y_here, x_here, y, x);
				int b = generate(y + 1, x + 1);
				ret = max(ret, generate(y + 1, x + 1) + gridSum(y_here, x_here, y, x));
			}
		}
	}

	return ret;
}

int gridSum(int y1, int x1, int y2, int x2)
{
	int ret = board[y2][x2];
	if (y1 > 0) ret -= board[y1 - 1][x2];
	if (x1 > 0) ret -= board[y2][x1 - 1];
	if (y1 > 0 && x1 > 0) ret += board[y1 - 1][x1 - 1];
	return ret;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 3