Submission #1100258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100258		vjudge1	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	336 KiB

joi2019_ho_t4

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <functional>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> coins(2 * N);
    
    for (int i = 0; i < 2 * N; i++) {
        cin >> coins[i].first >> coins[i].second;
    }

    vector<pair<int, int>> targets;
    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= 2; y++) {
            targets.push_back({x, y});
        }
    }

    vector<vector<int>> dist(2 * N, vector<int>(2 * N, 0));

    for (int i = 0; i < 2 * N; i++) {
        for (int j = 0; j < 2 * N; j++) {
            dist[i][j] = abs(coins[i].first - targets[j].first) + abs(coins[i].second - targets[j].second);
        }
    }

    vector<int> assignment(2 * N, -1);
    vector<bool> visited(2 * N, false);
    int min_cost = INT_MAX;

    function<void(int, int)> solve = [&](int idx, int current_cost) {
        if (idx == 2 * N) {
            min_cost = min(min_cost, current_cost);
            return;
        }

        for (int j = 0; j < 2 * N; j++) {
            if (!visited[j]) {
                visited[j] = true;
                solve(idx + 1, current_cost + dist[idx][j]);
                visited[j] = false;
            }
        }
    };

    solve(0, 0);
    
    cout << min_cost << endl;
    return 0;
}

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