This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 4e2 + 5;
const double eps = 1e-9;
int nx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int ny[4][2] = {{1, 3}, {2, 3}, {0, 2}, {0, 1}};
int a[MAXN][MAXN], w[MAXN][MAXN][2], b[MAXN][MAXN][2];
int n, m, par[MAXN][MAXN];
ll dp[MAXN][MAXN][4];
ll dijkstra(bool fl) {
mem(dp, 0x3f);
dp[0][0][1] = 0;
priority_queue<pair<pll,pll>,vector<pair<pll,pll>>,greater<pair<pll,pll>>> pq;
pq.push({{0,0},{0,1}});
while (!pq.empty()) {
pair<pll,pll> u = pq.top(); pq.pop();
ll cur = u.fi.fi;
int i = u.fi.se, j, k;
tie(j, k) = u.se;
if (dp[i][j][k] != cur)
continue;
if (fl && !(i == 0 && j == 0)) {
if ((1 - i > (k&1) || !b[i-1+(k&1)][j][0]) && dp[i][j][k^2] > cur) {
dp[i][j][k^2] = cur;
pq.push({{cur, i}, {j, k^2}});
}
if ((1 - j > (k/2) || !b[i][j-1+(k/2)][1]) && dp[i][j][k^1] > cur) {
dp[i][j][k^1] = cur;
pq.push({{cur, i}, {j, k^1}});
}
}
for (int l = 0; l < 4; l++) {
int ni = i + nx[l][0], nj = j + nx[l][1];
if (fl && ny[l][0] != k && ny[l][1] != k || ni < 0 || ni > n || nj < 0 || nj > m)
continue;
int nk = k ^ (fl ? (l & 1) + 1 : 0), nw = w[i - (l == 2)][j - (l == 3)][l & 1];
if (dp[ni][nj][nk] > cur + nw) {
dp[ni][nj][nk] = cur + nw;
pq.push({{cur+nw,ni},{nj,nk}});
par[ni][nj] = l;
}
}
}
return dp[0][0][2];
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
ni(a[i][j]);
for (int i = 0; i < 2; i++)
for (int j = 0; j < n + i; j++)
for (int k = 0; k < m + (1 - i); k++)
ni(w[j][k][i]);
dijkstra(0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!a[i][j])
continue;
int u = i, v = j;
while (!(u == 0 && v == 0)) {
int p = par[u][v];
if (b[u - (p == 0)][v - (p == 1)][p & 1] != 0)
break;
b[u - (p == 0)][v - (p == 1)][p & 1] = 1;
u -= nx[p][0];
v -= nx[p][1];
}
b[i][j][0] = b[i][j][1] = b[i][j+1][0] = b[i+1][j][1] = 1;
}
}
prl(dijkstra(1));
return 0;
}
Compilation message (stderr)
wall.cpp: In function 'll dijkstra(bool)':
wall.cpp:67:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (fl && ny[l][0] != k && ny[l][1] != k || ni < 0 || ni > n || nj < 0 || nj > m)
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
wall.cpp: In function 'int main()':
wall.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ni(n) scanf("%d", &(n))
~~~~~^~~~~~~~~~~~
wall.cpp:84:4: note: in expansion of macro 'ni'
ni(a[i][j]);
^~
wall.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ni(n) scanf("%d", &(n))
~~~~~^~~~~~~~~~~~
wall.cpp:88:5: note: in expansion of macro 'ni'
ni(w[j][k][i]);
^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |