oj.uz

Submission #28664

# Submission time Handle Problem Language Result Execution time Memory
28664 2017-07-16T08:31:39 Z 三( ε:)(#1146, xdoju, veckal, unused) Test Data Creation (FXCUP2_testdata) C++11
0 / 1
 0 ms 952 KB 
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

int p[90010];
int dp[90010][610]; // [ù ��° ��λ��� ��ġ][�� ��° ��λ��� ��ġ.. �ε� ù ��° ��λ��� ��ġ���� N���� ���� ������ ���� �ٷ�]

int fr[90010][610][2];
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){
          fr[i][j][0] = i - 1; fr[i][j][1] = j + 1; 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){
          fr[i][j][0] = i - M; fr[i][j][1] = j + M; 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){
          fr[i][j][0] = i; fr[i][j][1] = j - 1; 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){
          fr[i][j][0] = i; fr[i][j][1] = j - N; 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;

    int x_ = fr[x][y][0], y_ = fr[x][y][1];
    x = x_; y = y_;
  }

  for(int i = 0; i < N * M; i++){
    printf("%d ", ans[i]);
    if(i % N == N - 1) printf("\n");
  }
  return 0;
}

Compilation message

testdata.cpp: In function 'int main()':
testdata.cpp:13: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:14: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]);
                                                    ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -