Submission #9733

#	Time	Username	Problem	Language	Result	Execution time	Memory
9733		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
#define CACHE 123456789

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;

	for (int i = 0; i < 301; i++)
	{
		for (int j = 0; j < 301; j++)
			cache[i][j] = 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 here_y, int here_x)
{
	if (here_y == numOfY-1 && here_x == numOfX-1)
		return gridSum(here_y, here_x, here_y, here_x);

	int &ret = cache[here_y][here_x];

	if (ret != CACHE) return ret;

	ret = INF;

	for (int y = here_y; y < numOfY; y++)
	{
		for (int x = here_x; x < numOfX; x++)
		{
			int y_next = y + 1;
			int x_next = x + 1;

			if (y_next >= numOfY && x_next != numOfX) continue;
			if (y_next != numOfY && x_next >= numOfX) continue;
			if (y_next == numOfY && x_next == numOfX)
			{
				ret = max(ret, gridSum(here_y, here_x, y, x));
				continue;
			}
			int a = gridSum(here_y, here_x, y, x);
			int b = generate(y_next, x_next);
			ret = max(ret, gridSum(here_y, here_x, y, x) + generate(y_next, x_next));
		}
	}

	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