# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
28678 | 三( ε:) (#68) | Test Data Creation (FXCUP2_testdata) | C++11 | 993 ms | 216032 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
int p[90010];
int dp[90010][610]; // [ù ��° ��λ��� ��ġ][�� ��° ��λ��� ��ġ.. �ε� ù ��° ��λ��� ��ġ���� N���� ���� ������ ���� �ٷ�]
bool ans[90010];
int main(){
int N, M; scanf("%d%d", &N, &M);
for(int i = 0; i < N * M; i++) scanf("%d", &p[i]);
for(int i = 0; i < N * M; i++){
for(int j = 0; j <= 600; j++) dp[i][j] = INT_MAX;
}
dp[0][300] = p[0];
for(int i = 0; i < N * M; i++){
for(int j = 0; j <= 600; j++){
int v = INT_MAX;
int y = i + j - 300; if(y < 0 || y >= N * M) continue;
if(i == 0 && j == 300) continue;
// printf("%d, %d\n", i, y);
// i�� ���ʿ��� �̵� : (i - 1, i + j - 300) = [i - 1][j + 1]
if(i % M > 0 && j + 1 >= 0 && j + 1 <= 600 && dp[i - 1][j + 1] < INT_MAX){
// printf("%d %d, from i left\n", i, j);
int v_ = dp[i - 1][j + 1] + (j == 300 ? 0 : p[i]);
if(v_ < v) v = v_;
}
// i�� ������ �̵� : (i - M, i + j - 300) = [i - M][j + M]
if(i >= M && j + M >= 0 && j + M <= 600 && dp[i - M][j + M] < INT_MAX){
// printf("%d %d, from i up\n", i, j);
int v_ = dp[i - M][j + M] + (j == 300 ? 0 : p[i]);
if(v_ < v) v = v_;
}
// j�� ���ʿ��� �̵� : (i, i + j - 300 - 1) = [i][j - 1]
if(y % N > 0 && j - 1 >= 0 && j - 1 <= 600 && dp[i][j - 1] < INT_MAX){
// printf("%d %d, from j left\n", i, j);
int v_ = dp[i][j - 1] + (j == 300 ? 0 : p[y]);
if(v_ < v) v = v_;
}
// j�� ������ �̵� : (i, i + j - 300 - N) = [i][j - N]
if(y >= N && j - N >= 0 && j - N <= 600 && dp[i][j - N] < INT_MAX){
// printf("%d %d, from j up\n", i, j);
int v_ = dp[i][j - N] + (j == 300 ? 0 : p[y]);
if(v_ < v) v = v_;
}
dp[i][j] = v; // printf("%d %d : %d\n", i, j, v);
}
}
printf("%d\n", dp[N * M - 1][300]);
int x = N * M - 1, y = 300;
for(;;){
ans[x] = true; ans[x + y - 300] = true;
if(x == 0 && y == 300) break;
// x�� ���ʿ��� �̵� : (x - 1, x + y - 300) = [x - 1][y + 1]
if(x % M > 0 && y + 1 >= 0 && y + 1 <= 600 && dp[x - 1][y + 1] < INT_MAX){
// printf("%d %d, from x left\n", x, y);
int v_ = dp[x - 1][y + 1] + (y == 300 ? 0 : p[x]);
if(v_ == dp[x][y]){ x = x - 1; y = y + 1; continue; }
}
// x�� ������ �̵� : (x - M, x + y - 300) = [x - M][y + M]
if(x >= M && y + M >= 0 && y + M <= 600 && dp[x - M][y + M] < INT_MAX){
// printf("%d %d, from x up\n", x, y);
int v_ = dp[x - M][y + M] + (y == 300 ? 0 : p[x]);
if(v_ == dp[x][y]){ x = x - M; y = y + M; continue; }
}
// y�� ���ʿ��� �̵� : (x, x + y - 300 - 1) = [x][y - 1]
if((x + y - 300) % N > 0 && y - 1 >= 0 && y - 1 <= 600 && dp[x][y - 1] < INT_MAX){
// printf("%d %d, from y left\n", x, y);
int v_ = dp[x][y - 1] + (y == 300 ? 0 : p[(x + y - 300)]);
if(v_ == dp[x][y]){ x = x; y = y - 1; continue; }
}
// y�� ������ �̵� : (x, x + y - 300 - N) = [x][y - N]
if((x + y - 300) >= N && y - N >= 0 && y - N <= 600 && dp[x][y - N] < INT_MAX){
// printf("%d %d, from y up\n", x, y);
int v_ = dp[x][y - N] + (y == 300 ? 0 : p[(x + y - 300)]);
if(v_ == dp[x][y]){ x = x; y = y - N; continue; }
}
}
for(int i = 0; i < N * M; i++){
printf("%d ", ans[i]);
if(i % N == N - 1) printf("\n");
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |