#include <bits/stdc++.h>
#include <unistd.h>
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define lld long long
#define Inf 1000000000
#define get gett
using namespace std;
int N,M;
int a[302][302],d[302][302][602];
pii patht[302][302];
int dt[302][302],pathtt[302][302],print[302][302];
bool check[302][302],tcheck[302][302];
priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> q;
pii get;
vector<pii> tmp;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
struct data{
int x,y,z;
data(){}
data(int x,int y,int z):x(x),y(y),z(z){}
}path[302][302][602];
pii change(int i,int j){
int tmp = (i-1)*M+j-1;
return pii(tmp/N+1,tmp%N+1);
}
pii change2(int i,int j,int k){
// j <= N
if(j == N){
if(k <= j) return pii(i,k);
else return pii(i-(k-N),N);
}else{
if(k <= j) return pii(i,k);
else if(k <= N) return pii(i-1,k);
else return pii(i-(k-N)-1,N);
}
}
void init(int i,int j){
int x,y,range;
tmp.clear();
get = change(i,j);
x = get.first; y = get.second;
if(i == 1 && j <= N) range = j;
else if(y == N) range = N+x-1;
else range = N+x-2;
for(int k=1; k<=range; k++){
get = change2(x,y,k);
q.push({d[i][j][k],{get.first,get.second}});
tmp.pb(get);
check[get.first][get.second] = true;
}
}
int getvalue(int x,int y){
int tmp = (x-1)*N+y-1;
return a[tmp/M+1][tmp%M+1];
}
void calc(){
for(auto &i : tmp){
tcheck[i.first][i.second] = false;
dt[i.first][i.second] = Inf;
}
while(!q.empty()){
int value,x,y;
value = q.top().first;
x = q.top().second.first;
y = q.top().second.second;
q.pop();
if(tcheck[x][y]) continue;
tcheck[x][y] = true;
dt[x][y] = value;
for(int i=0; i<4; i++){
if(!check[x+dx[i]][y+dy[i]]) continue;
if(dt[x+dx[i]][y+dy[i]] > value+getvalue(x+dx[i],y+dy[i])){
dt[x+dx[i]][y+dy[i]] = value+getvalue(x+dx[i],y+dy[i]);
q.push({dt[x+dx[i]][y+dy[i]],{x+dx[i],y+dy[i]}});
patht[x+dx[i]][y+dy[i]] = {x,y};
}
}
}
for(auto &i : tmp){
check[i.first][i.second] = false;
int x,y;
vector<pii> memo;
x = i.first; y = i.second;
while(patht[x][y].first != 0){
memo.pb({x,y});
pii ttt = patht[x][y];
x = ttt.first; y = ttt.second;
}
for(auto &i : memo){
patht[i.first][i.second] = {x,y};
}
}
}
void calc2(int i,int j){
int x,y;
get = change(i,j);
x = get.first; y = get.second;
for(auto &i : tmp){
int t,tx,ty;
tx = patht[i.first][i.second].first;
ty = patht[i.first][i.second].second;
if(tx == x) t = ty;
else if(y == N){
t = N-tx+x;
}else{
if(tx== x-1) t = ty;
else t = N-tx+x-1;
}
pathtt[i.first][i.second] = t;
}
}
int lastd[302][302];
pii plpath[302][302];
void lastcalc(){
lastd[1][1] = 0;
for(int i=1; i<=M; i++){
for(int j=1; j<=N; j++){
if(i == 1 && j == 1) continue;
lastd[i][j] = Inf;
if(j > 1 && lastd[i][j] > lastd[i][j-1]){
lastd[i][j] = lastd[i][j-1];
plpath[i][j] = {i,j-1};
}
if(i > 1 && lastd[i][j] > lastd[i-1][j]){
lastd[i][j] = lastd[i-1][j];
plpath[i][j] = {i-1,j};
}
if(print[i][j] == 0) lastd[i][j] += getvalue(i,j);
}
}
int x,y;
x = M; y = N;
while(x != 0){
print[x][y] = true;
pii ttt = plpath[x][y];
x = ttt.first; y = ttt.second;
}
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d %d",&N,&M);
bool flag = false;
if(N > M){
swap(N,M);
flag = true;
}
for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++){
scanf("%d",&a[i][j]);
}
}
d[1][1][1] = a[1][1];
path[1][1][1] = data(0,0,0);
for(int i=2; i<=N; i++){
for(int j=1; j<=i; j++){
d[1][i][j] = d[1][i-1][1]+a[1][i];
path[1][i][j] = data(1,i-1,j);
}
}
for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++){
if(i == 1 && j <= N) continue;
int x,y,bx,by,range;
get = change(i,j);
x = get.first; y = get.second;
if(y == N) range = N+x-1;
else range = N+x-2;
for(int k=1; k<=range; k++) d[i][j][k] = Inf;
if(j != 1){
init(i,j-1);
get = change(i,j-1);
bx = get.first; by = get.second;
while(!(bx == x && by == y)){
if(!check[bx][by]){
check[bx][by] = true;
tmp.pb({bx,by});
}
by++;
if(by == N+1){
by = 1;
bx++;
}
}
for(int k=1; k<=range; k++){
get = change2(x,y,k);
if(!check[get.first][get.second]){
check[get.first][get.second] = true;
tmp.pb(get);
}
}
calc();
calc2(i,j-1);
for(int k=1; k<=range; k++){
get = change2(x,y,k);
int ttt;
if(k == y) ttt = 0;
else ttt = a[i][j];
if(d[i][j][k] > dt[get.first][get.second]+ttt){
d[i][j][k] = dt[get.first][get.second]+ttt;
path[i][j][k] = data(i,j-1,pathtt[get.first][get.second]);
}
}
}
if(i != 1){
init(i-1,j);
get = change(i-1,j);
bx = get.first; by = get.second;
while(!(bx == x && by == y)){
if(!check[bx][by]){
check[bx][by] = true;
tmp.pb({bx,by});
}
by++;
if(by == N+1){
by = 1;
bx++;
}
}
for(int k=1; k<=range; k++){
get = change2(x,y,k);
if(!check[get.first][get.second]){
check[get.first][get.second] = true;
tmp.pb(get);
}
}
calc();
calc2(i-1,j);
for(int k=1; k<=range; k++){
get = change2(x,y,k);
int ttt;
if(k == y) ttt = 0;
else ttt = a[i][j];
if(d[i][j][k] > dt[get.first][get.second]+ttt){
d[i][j][k] = dt[get.first][get.second]+ttt;
path[i][j][k] = data(i-1,j,pathtt[get.first][get.second]);
}
}
}
}
}
printf("%d\n",d[N][M][M]);
int x,y,z;
x = N; y = M; z = M;
while(x != 0){
data dtmp = path[x][y][z];
print[x][y] = 1;
x = dtmp.x; y = dtmp.y; z = dtmp.z;
}
vector<int> vprint;
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) vprint.pb(print[i][j]);
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) print[i][j] = 0;
for(int i=1; i<=M; i++){
for(int j=1; j<=N; j++) print[i][j] = vprint[(i-1)*N+j-1];
}
vprint.clear();
lastcalc();
for(int i=1; i<=M; i++) for(int j=1; j<=N; j++) vprint.pb(print[i][j]);
if(!flag) swap(N,M);
for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++) printf("%d ",vprint[(i-1)*M+j-1]);
puts("");
}
return 0;
}
Compilation message
testdata.cpp: In function 'int main()':
testdata.cpp:156:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&M);
^
testdata.cpp:164:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i][j]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1852 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
