Submission #1147502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147502		escobar_rohan	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	58 ms	11068 KiB

joi2019_ho_t4

import java.util.*;

class Main {
    static int totalCoins;
    static final long INF = (long) 1e18;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        totalCoins = scanner.nextInt();

        List<int[]> positions = new ArrayList<>();
        for (int i = 0; i < 2 * totalCoins; i++) {
            positions.add(new int[]{scanner.nextInt(), scanner.nextInt()});
        }
        scanner.close();

        DPCount(positions);
    }

    static void DPCount(List<int[]> positions) {
        Map<Set<Integer>, Long> coinStates = new HashMap<>();
        coinStates.put(new HashSet<>(), 0L);

        for (int placedCoins = 1; placedCoins <= 2 * totalCoins; placedCoins++) {
            Map<Set<Integer>, Long> newCoinStates = new HashMap<>();

            for (Map.Entry<Set<Integer>, Long> stateEntry : coinStates.entrySet()) {
                Set<Integer> currentPlacedCoins = stateEntry.getKey();
                long currentMoves = stateEntry.getValue();

                for (int coinIndex = 0; coinIndex < 2 * totalCoins; coinIndex++) {
                    if (!currentPlacedCoins.contains(coinIndex)) {
                        Set<Integer> newPlacedCoins = new HashSet<>(currentPlacedCoins);
                        newPlacedCoins.add(coinIndex);

                        int[] coinPosition = positions.get(coinIndex);
                        long moveCost;

                        if (placedCoins > totalCoins) {
                            moveCost = Math.abs(coinPosition[0] - (placedCoins - totalCoins))
                                    + Math.abs(coinPosition[1] - 2);
                        } else {
                            moveCost = Math.abs(coinPosition[0] - placedCoins)
                                    + Math.abs(coinPosition[1] - 1);
                        }

                        long updatedCost = currentMoves + moveCost;
                        long previousCost = newCoinStates.getOrDefault(newPlacedCoins, INF);
                        newCoinStates.put(newPlacedCoins, Math.min(previousCost, updatedCost));
                    }
                }
            }

            coinStates = newCoinStates;
        }

        long result = INF;
        for (long cost : coinStates.values()) {
            result = Math.min(result, cost);
        }

        System.out.println(result);
    }
}

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