| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 53322 | Namnamseo | 보물 찾기 (CEOI13_treasure2) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
void _f(int l, int r, int d, int u){
int& d=memo[l][r][d][u];
if(!d) d = countTreasure(l, r, d, u) + 1;
return d-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+1)/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);
}
}
}
}