Submission #42483

#	Time	Username	Problem	Language	Result	Execution time	Memory
42483		zaqq1414	보물 찾기 (CEOI13_treasure2)	C++14	68 / 100	2 ms	788 KiB

treasure

#include "treasure.h"
#define MAX	101

int cache[MAX][MAX];	// 해당 좌표 treasure 유무
int log[4][MAX][MAX];	// 기준 좌표에서 해당 좌표까지 treasurer 개수
int size;

int myCountTreasure(int side, int i, int j) {
	int &ret = log[side - 1][i][j];
	if (ret == -1) {
		if (side == 1) {	// 1사분면
			return ret = countTreasure(i, j, size, size);
		}
		else if (side == 2) {	// 2사분면
			return ret = countTreasure(i, 1, size, j);
		}
		else if (side == 3) {	// 3사분면
			return ret = countTreasure(1, j, i, size);
		}
		else { // 4사분면
			return  ret = countTreasure(1, 1, i, j);
		}
	}
	else
		return ret;
}

void side1dp() {
	for (int i = size / 2 - 1; i > 0; i--)
		cache[i][size / 2 - 1] = myCountTreasure(1, i, size / 2 - 1) - myCountTreasure(1, i + 1, size / 2 - 1) - myCountTreasure(1, i, size / 2) + myCountTreasure(1, i + 1, size / 2);
	for (int j = size / 2 - 1; j > 0; j--)
		cache[size / 2 - 1][j] = myCountTreasure(1, size / 2 - 1, j) - myCountTreasure(1, size / 2 - 1, j + 1) - myCountTreasure(1, size / 2, j) + myCountTreasure(1, size / 2, j + 1);

	for (int i = size / 2 - 2; i > 0; i--) {
		for (int j = size / 2 - 2; j > 0; j--) {
			cache[i][j] = myCountTreasure(1, i, j) - log[0][i + 1][j] - log[0][i][j + 1] + log[0][i + 1][j + 1];
		}
	}
}

void side2dp() {
	for (int i = size / 2 - 1; i > 0; i--)
		cache[i][size / 2] = myCountTreasure(2, i, size / 2) - myCountTreasure(2, i + 1, size / 2) - myCountTreasure(2, i, size / 2 - 1) + myCountTreasure(2, i + 1, size / 2 - 1);
	for (int j = size / 2; j <= size; j++)
		cache[size / 2 - 1][j] = myCountTreasure(2, size / 2 - 1, j) - myCountTreasure(2, size / 2 - 1, j - 1) - myCountTreasure(2, size / 2, j) + myCountTreasure(2, size / 2, j - 1);

	for (int i = size / 2 - 2; i > 0; i--) {
		for (int j = size / 2 + 1; j <= size; j++) {
			cache[i][j] = myCountTreasure(2, i, j) - log[1][i + 1][j] - log[1][i][j - 1] + log[1][i + 1][j - 1];
		}
	}
}

void side3dp() {
	for (int i = size / 2; i <= size; i++)
		cache[i][size / 2 - 1] = myCountTreasure(3, i, size / 2 - 1) - myCountTreasure(3, i - 1, size / 2 - 1) - myCountTreasure(3, i, size / 2) + myCountTreasure(3, i - 1, size / 2);
	for (int j = size / 2 - 1; j > 0; j--)
		cache[size / 2][j] = myCountTreasure(3, size / 2, j) - myCountTreasure(3, size / 2, j + 1) - myCountTreasure(3, size / 2 - 1, j) + myCountTreasure(3, size / 2 - 1, j + 1);

	for (int i = size / 2 + 1; i <= size; i++) {
		for (int j = size / 2 - 2; j > 0; j--) {
			cache[i][j] = myCountTreasure(3, i, j) - log[2][i - 1][j] - log[2][i][j + 1] + log[2][i - 1][j + 1];
		}
	}
}

void side4dp() {
	for (int i = size / 2; i <= size; i++)
		cache[i][size / 2] = myCountTreasure(4, i, size / 2) - myCountTreasure(4, i - 1, size / 2) - myCountTreasure(4, i, size / 2 - 1) + myCountTreasure(4, i - 1, size / 2 - 1);
	for (int j = size / 2; j <= size; j++)
		cache[size / 2][j] = myCountTreasure(4, size / 2, j) - myCountTreasure(4, size / 2, j - 1) - myCountTreasure(4, size / 2 - 1, j) + myCountTreasure(4, size / 2 - 1, j - 1);

	for (int i = size / 2 + 1; i <= size; i++) {
		for (int j = size / 2 + 1; j <= size; j++) {
			cache[i][j] = myCountTreasure(4, i, j) - myCountTreasure(4, i - 1, j) - myCountTreasure(4, i, j - 1) + myCountTreasure(4, i - 1, j - 1);
		}
	}
}

void dp() {
	if (size > 1) {
		cache[1][1] = myCountTreasure(4, size, size) - countTreasure(1, 2, size, size) - countTreasure(2, 1, size, size) + countTreasure(2, 2, size, size);
		log[3][1][1] = cache[1][1];
	}
	else {
		cache[1][1] = countTreasure(1, 1, 1, 1);
		return;
	}

	for (int i = 2; i <= size; i++)
		cache[i][1] = myCountTreasure(4, i, 1) - log[3][i - 1][1];
	for (int j = 2; j <= size; j++)
		cache[1][j] = myCountTreasure(4, 1, j) - log[3][1][j - 1];

	for (int i = 2; i <= size; i++) {
		for (int j = 2; j <= size; j++) {
			cache[i][j] = myCountTreasure(4, i, j) - log[3][i - 1][j] - log[3][i][j - 1] + log[3][i - 1][j - 1];
		}
	}
}

void findTreasure (int N) {
	// Initialize
	size = N;
	for (int i = 1; i <= size; i++)
		for (int j = 1; j <= size; j++) {
			for (int s = 0; s < 4; s++)
				log[s][i][j] = -1;
		}

	if (size > 10) {
		side1dp();
		side2dp();
		side3dp();
		side4dp();
	}
	else {
		dp();
	}

	for (int i = 1; i <= size; i++)
		for (int j = 1; j <= size; j++)
			if (cache[i][j])
				Report(i, j);
	return;
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:63:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         my_assert(strlen(A[i]+1) == N, "each line of the map must contain N zeroes or ones (before loop)");
                                  ^

• Subtask 1: 68 / 100