oj.uz

Submission #1100258

# Submission time Handle Problem Language Result Execution time Memory
1100258 2024-10-13T10:59:52 Z vjudge1 Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 1 ms 336 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -