#include <stdio.h>
#include <algorithm>
using namespace std;
int N, M, S[400][601], T[300*300];
int S1[400][601], S2[400][601];
bool ans[303*303];
void upd(int s[400][601], int i, int k, int t)
{
i %= 400;
if (s[i][k] == -1 || s[i][k] > t){
s[i][k] = t;
}
}
void go(int i1, int k1, int i2, int k2)
{
ans[i1] = ans[i1+k1-300] = ans[i2] = ans[i2+k2-300] = 1;
if (i1 == i2 && k1 == k2) return;
int r1 = (i1 + i2) / 2 + 150;
if (r1 > i2) r1 = i2;
int l2 = (i1 + i2) / 2 - 150;
if (l2 < i1) l2 = i1;
for (int i=0;i<400;i++) for (int k=0;k<=600;k++) S1[i][k] = -1;
S1[i1][k1] = T[i1] + (k1 != 300 ? T[i1+k1] : 0);
for (int i=i1;i<=r1;i++){
int xp = i / M, yp = i % M;
for (int k=0;k<=600;k++){
int &s = S1[i%400][k];
if (s != -1){
if (k >= 300){
if (xp + 1 < N) upd(S1, i+M, k-M, s+(k-M!=300?T[i+M]:0));
if (yp + 1 < M) upd(S1, i+1, k-1, s+(k-1!=300?T[i+1]:0));
}
else{
int xq = (i + k - 300) / N, yq = (i + k - 300) % N;
if (xq + 1 < M) upd(S1, i, k+N, s+(k+N!=300?T[i+k+N-300]:0));
if (yq + 1 < N) upd(S1, i, k+1, s+(k+1!=300?T[i+k+1-300]:0));
}
}
S1[(i+350)%400][k] = -1;
}
}
for (int i=0;i<400;i++) for (int k=0;k<=600;k++) S2[i][k] = -1;
S2[i2][k2] = T[i2] + (k2 != 300 ? T[i2+k2] : 0);
for (int i=i2;i>=l2;i--){
int xp = i / M, yp = i % M;
for (int k=600;k>=0;k--){
int &s = S2[i%400][k];
if (s != -1){
if (xp > 0 && k + M >= 300) upd(S2, i-M, k+M, s+(k+M!=300?T[i-M]:0));
if (yp > 0 && k + 1 >= 300) upd(S2, i-1, k+1, s+(k+1!=300?T[i-1]:0));
int xq = (i + k - 300) / N, yq = (i + k - 300) % N;
if (xq > 0 && k - N < 300) upd(S2, i, k-N, s+(k-N!=300?T[i+k-N-300]:0));
if (yq > 0 && k - 1 < 300) upd(S2, i, k-1, s+(k-1!=300?T[i+k-1-300]:0));
}
S2[(i+50)%400][k] = -1;
}
}
int ci, ck, mx = 0x7fffffff;
for (int i=l2;i<=r1;i++){
for (int k=0;k<=600;k++) if (S1[i%400][k] != -1 && S2[i%400][k] != -1){
if (i == i1 && k == k1) continue;
if (i == i2 && k == k2) continue;
int sum = S1[i%400][k] + S2[i%400][k] - T[i] - (k != 300 ? T[i+k] : 0);
if (mx > sum){
ci = i; ck = k;
mx = sum;
}
}
}
if (mx == 0x7fffffff) return;
go(i1,k1,ci,ck);
go(ci,ck,i2,k2);
}
int main()
{
scanf("%d %d", &M, &N);
for (int i=0;i<N*M;i++) scanf("%d", &T[i]);
for (int i=0;i<400;i++) for (int k=0;k<=600;k++) S[i][k] = -1;
S[0][300] = T[0];
int tp;
for (int i=0;i<N*M;i++){
int xp = i / M, yp = i % M;
for (int k=0;k<=600;k++){
int &s = S[i%400][k];
if (i == N*M-1 && k == 300) tp = s;
if (s != -1){
if (k >= 300){
if (xp + 1 < N) upd(S, i+M, k-M, s+(k-M!=300?T[i+M]:0));
if (yp + 1 < M) upd(S, i+1, k-1, s+(k-1!=300?T[i+1]:0));
}
else{
int xq = (i + k - 300) / N, yq = (i + k - 300) % N;
if (xq + 1 < M) upd(S, i, k+N, s+(k+N!=300?T[i+k+N-300]:0));
if (yq + 1 < N) upd(S, i, k+1, s+(k+1!=300?T[i+k+1-300]:0));
}
s = -1;
}
}
}
printf("%d\n", tp);
go(0,300,N*M-1,300);
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:85: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:86: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]);
^
testdata.cpp: In function 'void go(int, int, int, int)':
testdata.cpp:20:21: warning: 'ck' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (i1 == i2 && k1 == k2) return;
^
testdata.cpp:19:18: warning: 'ci' may be used uninitialized in this function [-Wmaybe-uninitialized]
ans[i1] = ans[i1+k1-300] = ans[i2] = ans[i2+k2-300] = 1;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4376 KB |
Correct |
| 2 |
Correct |
3 ms |
4376 KB |
Correct |
| 3 |
Incorrect |
0 ms |
4376 KB |
Wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
