#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<M; i++){
for(int j=0; j<N; j++)printf("%d ", ans[i*N+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]);
^
# |
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 |
306 ms |
216840 KB |
Correct |
6 |
Correct |
2826 ms |
216840 KB |
Correct |
7 |
Correct |
2436 ms |
216840 KB |
Correct |
8 |
Correct |
0 ms |
216840 KB |
Correct |
9 |
Correct |
0 ms |
216840 KB |
Correct |
10 |
Correct |
0 ms |
216840 KB |
Correct |
11 |
Correct |
0 ms |
216840 KB |
Correct |
12 |
Correct |
0 ms |
216840 KB |
Correct |
13 |
Correct |
3 ms |
216840 KB |
Correct |
14 |
Correct |
6 ms |
216840 KB |
Correct |
15 |
Correct |
16 ms |
216840 KB |
Correct |
16 |
Correct |
73 ms |
216840 KB |
Correct |
17 |
Correct |
479 ms |
216840 KB |
Correct |
18 |
Correct |
2853 ms |
216840 KB |
Correct |
19 |
Correct |
13 ms |
216840 KB |
Correct |
20 |
Correct |
1343 ms |
216840 KB |
Correct |
21 |
Correct |
506 ms |
216840 KB |
Correct |
22 |
Correct |
166 ms |
216840 KB |
Correct |
23 |
Correct |
429 ms |
216840 KB |
Correct |
24 |
Correct |
1703 ms |
216840 KB |
Correct |
25 |
Correct |
2733 ms |
216840 KB |
Correct |