제출 #53325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53325		Namnamseo	보물 찾기 (CEOI13_treasure2)	C++17	80 / 100	15 ms	12496 KiB

treasure

#include "treasure.h"

int ps1[105][105];
int ps2[105][105];
int ps3[105][105];
int ps4[105][105];
int exist[105][105];

int memo[101][101][101][101];
int _f(int l, int r, int d, int u){
	int& t=memo[l][r][d][u];
	if(!t) t = countTreasure(l, r, d, u) + 1;
	return t-1;
}

#define countTreasure _f

void s1(int N, int n, int m){
	if(m+1 <= N)
		for(int i=1; i<=n; ++i) ps1[i][m+1] = countTreasure(i, m+1, N, N);

	if(n+1 <= N)
		for(int i=1; i<=m; ++i) ps1[n+1][i] = countTreasure(n+1, i, N, N);

	if(n+1 <= N && m+1 <= N)
		ps1[n+1][m+1] = countTreasure(n+1, m+1, N, N);

	for(int i=n; 1<=i; --i){
		for(int j=m; 1<=j; --j){
			int t = countTreasure(i, j, N, N);
			ps1[i][j] = t;
			exist[i][j] = t - ps1[i+1][j] - ps1[i][j+1] + ps1[i+1][j+1];
		}
	}
}

#include <cstdio>
void s2(int N, int n, int m){
	int bot = 0;
	if(n+1 <= N && 1 <= m-1){
		bot = countTreasure(n+1, 1, N, m-1);
		ps2[n+1][m-1] = bot;
	}

	for(int i=n; 1<=i; --i){
		for(int j=1; j<m; ++j){
			ps2[i][j] = ps2[i+1][j] + ps2[i][j-1] - ps2[i+1][j-1] + exist[i][j];
		}
	}

	if(n+1 <= N)
		for(int i=m; i<=N; ++i) ps2[n+1][i] = countTreasure(n+1, 1, N, i);

	for(int i=n; 1<=i; --i){
		for(int j=m; j<=N; ++j){
			int t = countTreasure(i, 1, N, j);
			ps2[i][j] = t;
			exist[i][j] = t - ps2[i+1][j] - ps2[i][j-1] + ps2[i+1][j-1];
		}
	}
}

void s3(int N, int n, int m){
	if(n-1 >= 1){
		for(int i=1; i<n; ++i){
			for(int j=N; 1<=j; --j){
				ps3[i][j] = ps3[i-1][j] + ps3[i][j+1] - ps3[i-1][j+1] + exist[i][j];
			}
		}
	}

	if(m+1 <= N)
		for(int i=n; i<=N; ++i) ps3[i][m+1] = countTreasure(1, m+1, i, N);

	for(int i=n; i<=N; ++i){
		for(int j=m; 1<=j; --j){
			int t = countTreasure(1, j, i, N);
			ps3[i][j] = t;
			exist[i][j] = t - ps3[i-1][j] - ps3[i][j+1] + ps3[i-1][j+1];
		}
	}
}

void s4(int N, int n, int m){
	for(int i=1; i<n; ++i){
		for(int j=1; j<=N; ++j){
			ps4[i][j] = ps4[i-1][j]+ps4[i][j-1]-ps4[i-1][j-1]+exist[i][j];
		}
	}

	for(int i=n; i<=N; ++i){
		for(int j=1; j<m; ++j){
			ps4[i][j] = ps4[i-1][j]+ps4[i][j-1]-ps4[i-1][j-1]+exist[i][j];
		}
	}

	for(int i=n; i<=N; ++i){
		for(int j=m; j<=N; ++j){
			int t = countTreasure(1, 1, i, j);
			ps4[i][j] = t;
			exist[i][j] = t - ps4[i-1][j] - ps4[i][j-1] + ps4[i-1][j-1];
		}
	}
}

void findTreasure (int N) {
	int mid = (N)/2;
	s1(N, mid, mid);
	s2(N, mid, mid+1);
	s3(N, mid+1, mid);
	s4(N, mid+1, mid+1);

	for(int i=1; i<=N; ++i){
		for(int j=1; j<=N; ++j){
			if(exist[i][j]){
				Report(i, j);
			}
		}
	}
}

• Subtask 1: 80 / 100