Submission #28678

#TimeUsernameProblemLanguageResultExecution timeMemory
28678三( ε:) (#68)Test Data Creation (FXCUP2_testdata)C++11
1 / 1
993 ms216032 KiB
#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)

testdata.cpp: In function 'int main()':
testdata.cpp:11:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int N, M; scanf("%d%d", &N, &M);
                                  ^
testdata.cpp:12:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 0; i < N * M; i++) scanf("%d", &p[i]);
                                                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...