| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1122745 | AnhPham | Wall (CEOI14_wall) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
const int MOD = (int)1e9 + 7;
const int INF = (int)4e18 + 18;
void solve();
int32_t main() {
#define CODE ""
if (fopen(CODE".inp", "r"))
freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
int testcases = 1;
#define multitest 0
if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); }
}
/** [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] **/
/** The Last Dance **/
const int mxN = 404;
int N, M;
int A[mxN][mxN];
int ver[mxN][mxN], hor[mxN][mxN];
namespace sub1 {
bool check_condition() {
int cnt = 0;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
cnt += A[i][j] == 1;
return cnt <= 10 && N <= 40 && M <= 40;
}
int mask_ver[44][44];
int nodes, id[44][44][1 << 11];
vector <pair <int, int>> adj[44 * 44];
int dst[mxN * mxN * (1 << 11)];
void add_edge(int u, int v, int c) {
adj[u].push_back({ c, v });
adj[v].push_back({ c, u });
}
void solve() {
vector <pair <int, int>> points;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
if (A[i][j] == 1)
points.push_back({ i, j });
for (int i = 0; i < N; ++i)
for (int j = 0; j <= M; ++j)
for (int k = 0; k < sz(points); ++k)
if (points[k].first == i + 1 && points[k].second <= j)
mask_ver[i][j] |= 1 << k;
for (int i = 0; i <= N; ++i)
for (int j= 0; j <= M; ++j)
for (int mask = 0; mask < (1 << sz(points)); ++mask)
id[i][j][mask] = ++nodes;
for (int i = 0; i <= N; ++i)
for (int j = 0; j <= M; ++j)
for (int mask = 0; mask < (1 << sz(points)); ++mask) {
if (i < N)
add_edge(id[i][j][mask], id[i + 1][j][mask ^ mask_ver[i][j]], ver[i][j]);
if (j < N)
add_edge(id[i][j][mask], id[i][j + 1][mask], hor[i][j]);
}
for (int i = 1; i <= nodes; ++i)
dst[i] = 1ll << 60;
priority_queue <pair <int, int>> pq;
pq.push ({ dst[id[0][0][0]] = 0, id[0][0][0] });
while (sz(pq)) {
auto [du, u] = pq.top(); pq.pop();
if (dst[u] != -du)
continue;
for (auto [c, v] : adj[u])
if (dst[v] > dst[u] + c) {
dst[v] = dst[u] + c;
pq.push({ -dst[v], v });
}
}
cout << dst[id[0][0][(1 << sz(points)) - 1]] << '\n';
}
}
void solve() {
cin >> N >> M;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
cin >> A[i][j];
for (int i = 0; i < N; ++i)
for (int j = 0; j <= M; ++j)
cin >> ver[i][j];
for (int i = 0; i <= N; ++i)
for (int j = 0; j < M; ++j)
cin >> hor[i][j];
if (sub1 :: check_condition())
sub1 :: solve();
}