#include <stdio.h>
int N, M, S[300*300][601], T[300*300];
bool wh[300*300][601], mv[300*300][601], ans[300*300];
void upd(int i, int k, int t, bool w, bool m)
{
if (S[i][k] == -1 || S[i][k] > t){
S[i][k] = t;
wh[i][k] = w;
mv[i][k] = m;
}
}
int main()
{
scanf("%d %d", &M, &N);
for (int i=0;i<N*M;i++) scanf("%d", &T[i]);
for (int i=0;i<N*M;i++) for (int k=0;k<=600;k++) S[i][k] = -1;
S[0][300] = T[0];
for (int i=0;i<N*M;i++){
int xp = i / M, yp = i % M;
for (int k=0;k<=600;k++) if (S[i][k] != -1){
if (k >= 300){
if (xp + 1 < N) upd(i+M,k-M,S[i][k]+(k-M!=300?T[i+M]:0),0,0);
if (yp + 1 < M) upd(i+1,k-1,S[i][k]+(k-1!=300?T[i+1]:0),0,1);
}
else{
int xq = (i + k - 300) / N, yq = (i + k - 300) % N;
if (xq + 1 < M) upd(i,k+N,S[i][k]+(k+N!=300?T[i+k+N-300]:0),1,0);
if (yq + 1 < N) upd(i,k+1,S[i][k]+(k+1!=300?T[i+k+1-300]:0),1,1);
}
}
}
printf ("%d\n",S[N*M-1][300]);
int i = N * M - 1, k = 300;
while (1){
ans[i] = ans[i+k-300] = 1;
if (!wh[i][k]){
if (!mv[i][k]) i -= M, k += M;
else i--, k++;
}
else{
if (!mv[i][k]) k -= N;
else k--;
}
if (i == 0 && k == 300) break;
}
ans[0] = 1;
for (int i=0;i<N;i++){
for (int j=0;j<M;j++) printf("%d%c",ans[i*M+j]?1:0,j+1<M?' ':'\n');
}
return 0;
}
Compilation message
testdata.cpp: In function 'int main()':
testdata.cpp:17:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &M, &N);
^
testdata.cpp:18:44: 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", &T[i]);
^
| # |
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 |
- |
