oj.uz

Submission #53325

# Submission time Handle Problem Language Result Execution time Memory
53325 2018-06-29T09:46:49 Z Namnamseo Treasure (different grader from official contest) (CEOI13_treasure2) C++17
80 / 100
 15 ms 12496 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 376 KB Output is partially correct - N = 5, K = 309, score = 8
2 Partially correct 3 ms 656 KB Output is partially correct - N = 10, K = 4551, score = 8
3 Partially correct 3 ms 832 KB Output is partially correct - N = 15, K = 22459, score = 8
4 Partially correct 2 ms 908 KB Output is partially correct - N = 16, K = 29121, score = 8
5 Partially correct 7 ms 4236 KB Output is partially correct - N = 55, K = 4007559, score = 8
6 Partially correct 7 ms 6008 KB Output is partially correct - N = 66, K = 8309071, score = 8
7 Partially correct 10 ms 7564 KB Output is partially correct - N = 77, K = 15387609, score = 8
8 Partially correct 15 ms 9908 KB Output is partially correct - N = 88, K = 26250225, score = 8
9 Partially correct 14 ms 12180 KB Output is partially correct - N = 99, K = 42039553, score = 8
10 Partially correct 15 ms 12496 KB Output is partially correct - N = 100, K = 43767501, score = 8