Submission #1320732

#TimeUsernameProblemLanguageResultExecution timeMemory
1320732vaishakhvCoin Collecting (JOI19_ho_t4)C++20
8 / 100
71 ms32352 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define eb emplace_back // faster than push_back xD

// pbds UwU
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define oset tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> // use pair for ms

// my io library :D
#define m1(x) template<class T, class... U> void x(T&& a, U&&... b)
#define m2(x) (ll[]){(x forward<U>(b),0)...}

m1(pr){cout << forward<T>(a);  m2(cout << " " <<); cout << "\n";}
m1(re){cin >> forward<T>(a); m2(cin >>);}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

    ll n; re(n);
    vector<pair<ll,ll>> points(2*n);
    for (ll i{}; i < 2*n; i++){
        ll x, y; re(x, y);
        points[i] = {x,y};
    }

    vector<pair<ll,ll>> target;
    for (ll x = 1; x <= n; x++) {
        target.eb(x, 1);
    }
    for (ll x = 1; x <= n; x++) {
        target.eb(x, 2);
    }

    vector<vector<ll>> cost(2*n, vector<ll>(2*n));

    for (ll i{}; i < 2*n; i++) {
        for (ll j{}; j < 2*n; j++) {
            cost[i][j] = abs(points[i].first - target[j].first)
                    + abs(points[i].second - target[j].second);
        }
    }

    vector<ll> dp(1<<(2*n), 1e18);
    dp[0] = 0;
    for (ll mask{}; mask < 1<<(2*n); mask++){
        ll i = __builtin_popcountll(mask);

        for (ll j{}; j < 2*n; j++){
            if (!(mask & (1<<j))){
                dp[mask | (1<<j)] = min(dp[mask | (1<<j)], dp[mask]+cost[i][j]);
            }
        }
    }

    pr(dp[(1<<(2*n)) - 1]);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...