oj.uz

Submission #27017

# Submission time Handle Problem Language Result Execution time Memory
27017 2017-07-08T13:11:48 Z 검수팍(#1115) Test Data Creation (FXCUP2_testdata) C++
0 / 1
 3000 ms 216840 KB 
#include<stdio.h>

int N, M, NM, ba[90090], ans[90090], D[90090][611];

int dy(int x, int y){
	int df=x-y+NM;
	if(x==N*M-1 && y==N*M-1)return ba[x];
	if(D[x][df])return D[x][df];

	int dap=0x7fffffff, gap;
	if(x<y){
		if(x%N != N-1){
			gap = ba[x]+dy(x+1, y);
			if(dap > gap)dap = gap;
		}
		if(x+N < N*M){
			gap = ba[x]+dy(x+N, y);
			if(dap > gap)dap = gap;
		}
	}
	else{
		if(y%M != M-1){
			gap = ba[y]+dy(x, y+1);
			if(x == y)gap -= ba[y];
			if(dap > gap)dap = gap;
		}
		if(y+M < N*M){
			gap = ba[y]+dy(x, y+M);
			if(x == y)gap -= ba[y];
			if(dap > gap)dap = gap;
		}
	}
	return D[x][df]=dap;
}

void rev(int x, int y){
	ans[x]=ans[y]=1;
	if(x==N*M-1 && y==N*M-1)return;

	if(x<y){
		if(x%N != N-1 && dy(x,y) == ba[x]+dy(x+1, y))rev(x+1, y);
		else rev(x+N, y);
	}
	else{
		if(y%M != M-1 && dy(x,y) == (x==y?0:ba[y]) + dy(x, y+1))rev(x, y+1);
		else rev(x, y+M);
	}
}


int main(){
	scanf("%d%d", &N, &M);
	NM = N<M?M:N;
	for(int i=0; i<N*M; i++)scanf("%d", &ba[i]);
	printf("%d\n", dy(0, 0)); rev(0, 0);
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++)printf("%d ", ans[i*M+j]);
		puts("");
	}
	return 0;
}

Compilation message

testdata.cpp: In function 'int main()':
testdata.cpp:52:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
testdata.cpp:54:45: 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", &ba[i]);
                                             ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216840 KB Correct
2 Correct 0 ms 216840 KB Correct
3 Correct 0 ms 216840 KB Correct
4 Correct 9 ms 216840 KB Correct
5 Correct 259 ms 216840 KB Correct
6 Correct 1523 ms 216840 KB Correct
7 Execution timed out 3000 ms 216840 KB Execution timed out
8 Halted 0 ms 0 KB -