Submission #587046

#	Time	Username	Problem	Language	Result	Execution time	Memory
587046		Justin1	Coin Collecting (JOI19_ho_t4)	C++14	8 / 100	284 ms	16784 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct pt{
    ll x, y;
};

ll n,m,k,x,y,z;
ll dp[2 << 21], dig[2 << 21];
pt ar[200005], tar[200005];

void cal(ll x, ll & y) {
    while (x) x &= x-1, y++;
}

int dis(pt x, pt y) {
    return abs(x.x - y.x) + abs(x.y - y.y);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) tar[i] = {i,1};
    for (int i = 1; i <= n; i++) tar[i+n] = {i,2};
    n *= 2;
    for (int i = 1; i <= n; i++) {
        cin >> ar[i].x >> ar[i].y;
    }
    for (int i = 1; i < 1 << n; i++) cal(i,dig[i]);
    for (int c = 1; c <= n; c++) {
        for (int i = 1; i < 1 << n; i++) {
            if (dig[i] != c) continue;
            dp[i] = 1e18;
            for (int j = 1; j <= n; j++) {
                if (~i & (1 << (j-1))) continue;
                dp[i] = min(dp[i],dis(tar[c],ar[j]) + dp[i ^ (1 << (j-1))]);
            }
        }
    }
    cout << dp[(1 << n) - 1] << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63