| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 94870 | rhdmstjr | 보물 찾기 (CEOI13_treasure2) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "treasure.h"
#include <vector>
using namespace std;
#define MAX_N 104
int pSum[MAX_N][MAX_N]; // [1, 100]
bool isTreasure(int r, int c) {
return pSum[r][c] - pSum[r-1][c] - pSum[r][c-1] + pSum[r-1][c-1];
}
int memo[MAX_N][MAX_N] = {-1, };
int countTreasure(int r1, int c1, int r2, int c2) {
int &m = memo[]
}
int n;
void initPSum() {
// init pSum
// 일단은 한 방향 + 최적화 없이
pSum[n][n] = countTreasure(1, 1, n, n);
int half_boundary = (n + 1) / 2;
for(int i = 1; i <= n; i++) {
if (half_boundary < i ){
pSum[i][n] = countTreasure(1, 1, i, n);
pSum[n][i] = countTreasure(1, 1, n, i);
}
else {
pSum[i][n] = pSum[n][n] - countTreasure(i + 1, 1, n, n);
pSum[n][i] = pSum[n][n] - countTreasure(1, i + 1, n, n);
}
}
if ((n & 1) == 0) half_boundary++;
for(int r = 1; r < n; r++) {
for(int c = 1; c < n; c++) {
if (r < half_boundary) {
if (c < half_boundary) {
pSum[r][c] = countTreasure(r + 1, c + 1, n, n) + pSum[r][n] + pSum[n][c] - pSum[n][n];
}
else {
pSum[r][c] = pSum[n][c] - countTreasure(r + 1, 1, n, c);
}
} else {
if (c < half_boundary) {
pSum[r][c] = pSum[r][n] - countTreasure(1, c + 1, r, n);
}
else{
pSum[r][c] = countTreasure(1, 1, r, c);
}
}
}
}
}
void findTreasure (int N) {
n = N;
initPSum();
for(int r = 1; r <= N; r++) {
for(int c = 1; c <= N; c++) {
if (isTreasure(r, c)) {
Report(r, c);
}
}
}
}