Submission #1147501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147501		escobar_rohan	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	58 ms	11344 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();

        if (totalCoins <= 20) {
            DPCount(positions);
        } else {
            greedyCount(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);
    }

    static void greedyCount(List<int[]> positions) {
        int[][] targetCounts = new int[totalCoins + 1][2];
        long movesCount = 0;

        for (int[] coinPosition : positions) {
            int x = coinPosition[0], y = coinPosition[1];

            if (x < 1) {
                movesCount += (1 - x);
                x = 1;
            } else if (x > totalCoins) {
                movesCount += (x - totalCoins);
                x = totalCoins;
            }
            if (y < 1) {
                movesCount += (1 - y);
                y = 1;
            } else if (y > 2) {
                movesCount += (y - 2);
                y = 2;
            }

            targetCounts[x][y - 1]++;
        }

        for (int i = 1; i <= totalCoins; i++) {
            targetCounts[i][0] += targetCounts[i - 1][0] - 1;
            targetCounts[i][1] += targetCounts[i - 1][1] - 1;

            if (targetCounts[i][0] > 0 && targetCounts[i][1] < 0) {
                int movesNeeded = Math.min(targetCounts[i][0], -targetCounts[i][1]);
                movesCount += movesNeeded;
                targetCounts[i][0] -= movesNeeded;
                targetCounts[i][1] += movesNeeded;
            }
            movesCount += Math.abs(targetCounts[i][0]) + Math.abs(targetCounts[i][1]);
        }
        System.out.println(movesCount);
    }
}

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