Submission #1236933

#TimeUsernameProblemLanguageResultExecution timeMemory
1236933kaiboyWall (CEOI14_wall)C++20
30 / 100
825 ms20836 KiB
#include <algorithm> #include <iostream> using namespace std; const int N = 40; const int M = 40; const int K = 10; const int CNT = (N + 1) * (M + 1) << K; const long long INF = 0x3f3f3f3f3f3f3f3fLL; int aa[N][M], wwi[N][M + 1], wwj[N + 1][M]; long long dd[N + 1][M + 1][1 << K]; int pq[CNT], iq[CNT + 1], cnt; int m, k; int encode(int i, int j, int b) { return i * (m + 1) + j << k ^ b; } void decode(int ijb, int &i, int &j, int &b) { b = ijb & (1 << k) - 1, ijb >>= k; j = ijb % (m + 1), ijb /= m + 1; i = ijb; } bool lt(int ijb0, int ijb1) { int i0, j0, b0; decode(ijb0, i0, j0, b0); int i1, j1, b1; decode(ijb1, i1, j1, b1); return dd[i0][j0][b0] < dd[i1][j1][b1]; } int p2(int p) { return (p <<= 1) > cnt ? 0 : p + lt(iq[p ^ 1], iq[p]); } void pq_up(int i) { int j, p, q; for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_dn(int i) { int j, p, q; for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_add_last(int i) { iq[pq[i] = ++cnt] = i; } int pq_remove_first() { int i = iq[1], j = iq[cnt--]; if (i != j) pq[j] = 1, pq_dn(j); pq[i] = 0; return i; } int main() { int n; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> aa[i][j]; for (int i = 0; i < n; i++) for (int j = 0; j <= m; j++) cin >> wwi[i][j]; for (int i = 0; i <= n; i++) for (int j = 0; j < m; j++) cin >> wwj[i][j]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) if (aa[i][j]) aa[i][j] = 1 << k++; if (i) for (int j = 0; j < m; j++) aa[i][j] ^= aa[i - 1][j]; } for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) for (int b = 0; b < 1 << k; b++) dd[i][j][b] = INF; dd[0][0][0] = 0, pq_add_last(encode(0, 0, 0)); while (cnt) { int ijb = pq_remove_first(), i, j, b; decode(ijb, i, j, b); long long d = dd[i][j][b]; if (i) { int i_ = i - 1, j_ = j, b_ = b, ijb_ = encode(i_, j_, b_); long long d_ = d + wwi[i - 1][j]; if (dd[i_][j_][b_] > d_) { if (dd[i_][j_][b_] == INF) pq_add_last(ijb_); dd[i_][j_][b_] = d_, pq_up(ijb_); } } if (i < n) { int i_ = i + 1, j_ = j, b_ = b, ijb_ = encode(i_, j_, b_); long long d_ = d + wwi[i][j]; if (dd[i_][j_][b_] > d_) { if (dd[i_][j_][b_] == INF) pq_add_last(ijb_); dd[i_][j_][b_] = d_, pq_up(ijb_); } } if (j) { int i_ = i, j_ = j - 1, b_ = b ^ (i ? aa[i - 1][j - 1] : 0), ijb_ = encode(i_, j_, b_); long long d_ = d + wwj[i][j - 1]; if (dd[i_][j_][b_] > d_) { if (dd[i_][j_][b_] == INF) pq_add_last(ijb_); dd[i_][j_][b_] = d_, pq_up(ijb_); } } if (j < m) { int i_ = i, j_ = j + 1, b_ = b ^ (i ? aa[i - 1][j] : 0), ijb_ = encode(i_, j_, b_); long long d_ = d + wwj[i][j]; if (dd[i_][j_][b_] > d_) { if (dd[i_][j_][b_] == INF) pq_add_last(ijb_); dd[i_][j_][b_] = d_, pq_up(ijb_); } } } cout << dd[0][0][(1 << k) - 1] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...