oj.uz

답안 #28466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
28466 2017-07-16T06:16:06 Z Shocking Hot(#1200, khsoo01) Test Data Creation (FXCUP2_testdata) C++14
0 / 1
 0 ms 215420 KB 
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9, B = 301;

int n, m, a[90001], ans[90001], dt[90001][605];
bool f;

bool valid (int X, int Y) {
	if(!(1 <= X && X <= n*m && B-n <= Y && Y <= B+n)) return false;
	if(!(1 <= X+Y-B && X+Y-B <= n*m)) return false;
	return true;
}

void track (int X, int Y) {
	if(X == 1 && Y == B) return;
	int i, j;
	ans[X] = 1; ans[X+Y-B] = 1;
	i = X - n, j = Y + n;
	if(valid(i, j) && i+n <= n*m && j-n >= B-n && dt[i][j] + (j-n != B)*a[i+n] == dt[X][Y]) {
		track(i, j); return;
	}
	i = X - 1, j = Y + 1;
	if(valid(i, j) && i%n && j-1 >= B-n && dt[i][j] + (j-1 != B)*a[i+1] == dt[X][Y]) {
		track(i, j); return;
	}
	i = X, j = Y-m;
	if(valid(i, j) && j+m <= B+n && i+j+m-B <= n*m && dt[i][j] + (j+m != B)*a[i+j+m-B] == dt[X][Y]) {
		track(i, j); return;
	}
	i = X, j = Y-1;
	if(valid(i, j) && j+1 <= B+n && (i+j-B)%m && dt[i][j] + (j+1 != B)*a[i+j+1-B] == dt[X][Y]) {
		track(i, j); return;
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	if(n < m) {swap(n, m); f = true;}
	for(int i=1;i<=n*m;i++) {
		scanf("%d",&a[i]);
		for(int j=B-n-1;j<=B+n+1;j++) {
			dt[i][j] = inf;
		}
	}
	dt[1][B] = a[1];
	for(int i=1;i<=n*m;i++) {
		for(int j=B-n;j<=B+n;j++) {
			if(i+j-B < 1 || i+j-B > n*m) continue;
			if(i+n <= n*m && j-n >= B-n) {
				dt[i+n][j-n] = min(dt[i+n][j-n], dt[i][j] + (j-n != B)*a[i+n]);
			}
			if(i%n && j-1 >= B-n) {
				dt[i+1][j-1] = min(dt[i+1][j-1], dt[i][j] + (j-1 != B)*a[i+1]);
			}
			if(j+m <= B+n && i+j+m-B <= n*m) {
				dt[i][j+m] = min(dt[i][j+m], dt[i][j] + (j+m != B)*a[i+j+m-B]);
			}
			if(j+1 <= B+n && (i+j-B)%m) {
				dt[i][j+1] = min(dt[i][j+1], dt[i][j] + (j+1 != B)*a[i+j+1-B]);
			}
		}
	}
	printf("%d\n",dt[n*m][B]);
	track(n*m, B);
	if(f) swap(n, m);
	for(int i=1;i<=m;i++) {
		for(int j=1;j<=n;j++) {
			printf("%d ",ans[n*(i-1)+j]);
		}
		puts("");
	}
}

Compilation message

testdata.cpp: In function 'int main()':
testdata.cpp:38:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
testdata.cpp:41:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 215420 KB Wrong
2 Halted 0 ms 0 KB -