Submission #42335

#	Time	Username	Problem	Language	Result	Execution time	Memory
42335		zaqq1414	Treasure (different grader from official contest) (CEOI13_treasure2)	C++14	44 / 100	2 ms	732 KiB

treasure

#include "treasure.h"
#define MAX	101

int cache[MAX][MAX];	// 해당 좌표 treasure 유무
int log[MAX][MAX];	// (1,1) 에서 해당 좌표까지 있는 treasurer 개수
int size;

int myCountTreasure(int i, int j) {
	int &ret = log[i][j];
	if (ret == -1)
		return  ret = countTreasure(1, 1, i, j);
	else
		return ret;
}

void dp() {
	if (size > 1) {
		cache[1][1] = myCountTreasure(size, size) - countTreasure(1, 2, size, size) - countTreasure(2, 1, size, size) + countTreasure(2, 2, size, size);
		log[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(i, 1) - log[i-1][1];
	for (int j = 2; j <= size; j++)
		cache[1][j] = myCountTreasure(1, j) - log[1][j-1];

	for (int i = 2; i <= size; i++) {
		for (int j = 2; j <= size; j++) {
			cache[i][j] = myCountTreasure(i, j) - log[i - 1][j] - log[i][j - 1] + log[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++)
			log[i][j] = -1;

	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: 44 / 100