Submission #1122744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122744		AnhPham	Wall (CEOI14_wall)	C++20	0 / 100	33 ms	21152 KiB

wall

#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[44 * 44];

    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();
}

Compilation message (stderr)

wall.cpp: In function 'int32_t main()':
wall.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:17:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40