Submission #73391813

---

Source Code Expand

#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <random>
#include <chrono>
#include <map>
#include <set>
#include <ctime>
#include <bitset>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

#define lp p << 1
#define rp p << 1 | 1
#define lowbit(x) (x & (-x))
#define i128 __int128
#define ent "\n"
#define cc(x) cout << fixed << setprecision(x)

const int mod = 1e9 + 7;
const double eps = 1e-8;
const int oo = 0x3f3f3f3f;
const LL INF = 2e18;

void solve() {
    // auto seed = std::chrono::system_clock::now().time_since_epoch().count();
    // mt19937_64 gen(seed);  
    // uniform_int_distribution<LL> dist(1, 1e18);

    // freopen("114514.in", "r", stdin);
    // freopen("114514.out", "w", stdout);
    
    /*   /\_/\
    *   (= ._.)
    *   / >  \>
    */

    int n, m; cin >> n >> m;
    LL s, t; cin >> s >> t;
    int c1 = s % n; if (c1 == 0) c1 = n;
    int r1 = (s - c1) / n + 1;
    int c2 = t % n; if (c2 == 0) c2 = n;
    int r2 = (t - c2) / n + 1;
    vector<LL> p(m + 1);
    vector<int> r(m + 1), c(m + 1);
    for (int i = 1; i <= m; ++ i) {
        cin >> p[i];
        c[i] = p[i] % n; if (c[i] == 0) c[i] = n;
        r[i] = (p[i] - c[i]) / n + 1;
    }
    if (m == 0) {
        cout << (LL)abs(r1 - r2) + abs(c1 - c2) << ent;
        return;
    }
    vector<vector<LL>> dp(1 << m, vector<LL>(m + 1, INF));
    for (int i = 1; i < 1 << m; ++ i) {
        for (int j = 0; j < m; ++ j) {
            if (i >> j & 1) {
                int k = i ^ (1 << j);
                if (k == 0) {
                    dp[i][j + 1] = min(dp[i][j + 1], (LL)abs(r[j + 1] - r1) + (LL)abs(c[j + 1] - c1));
                } else {
                    for (int h = 0; h < m; ++ h) {
                        if (k >> h & 1) {
                            dp[i][j + 1] = min(dp[i][j + 1], dp[k][h + 1] + (LL)abs(r[j + 1] - r[h + 1]) + (LL)abs(c[j + 1] - c[h + 1]));
                        }
                    }
                }
            }
        }
    }

    LL res = INF;
    for (int i = 1; i <= m; ++ i) res = min(res, dp[(1 << m) - 1][i] + (LL)abs(r[i] - r2) + (LL)abs(c[i] - c2));
    cout << res << ent;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int T = 1;
    bool flag = 0;
    if (flag) cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result