Submission #1147701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147701		mrariel	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	83 ms	13176 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {
    public static int minTotalMoves(int n, List<int[]> coins) {
        List<int[]> targets = new ArrayList<>();
        
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= 2; y++) {
                targets.add(new int[]{x, y});
            }
        }
        
        coins.sort(Comparator.comparingInt((int[] coin) -> coin[0]).thenComparingInt(coin -> coin[1]));
        targets.sort(Comparator.comparingInt((int[] target) -> target[0]).thenComparingInt(target -> target[1]));
        
        int[][] cost = new int[2 * n][2 * n];
        for (int i = 0; i < 2 * n; i++) {
            for (int j = 0; j < 2 * n; j++) {
                cost[i][j] = Math.abs(coins.get(i)[0] - targets.get(j)[0]) + Math.abs(coins.get(i)[1] - targets.get(j)[1]);
            }
        }
        
        int maxState = (int) Math.pow(3, 2 * n);
        int[] dp = new int[maxState];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int mask = 0; mask < maxState; mask++) {
            int[] assigned = new int[2 * n];
            
            int currentMask = mask;
            for (int i = 0; i < 2 * n; i++) {
                assigned[i] = currentMask % 3;
                currentMask /= 3;
            }
            
            int x = 0;
            for (int i = 0; i < 2 * n; i++) {
                if (assigned[i] != 0) {
                    x++;
                }
            }
            if (x >= 2 * n) {
                continue;
            }
            
            for (int j = 0; j < 2 * n; j++) {
                if (assigned[j] == 0) {
                    for (int newTarget = 1; newTarget <= 2; newTarget++) {
                        int newMask = mask + newTarget * (int) Math.pow(3, j);
                        dp[newMask] = Math.min(dp[newMask], dp[mask] + cost[x][j]);
                    }
                }
            }
        }
        
        return dp[maxState - 1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        List<int[]> coins = new ArrayList<>();
        
        for (int i = 0; i < 2 * n; i++) {
            String[] parts = scanner.nextLine().split(" ");
            coins.add(new int[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])});
        }
        
        System.out.println(minTotalMoves(n, coins));
        scanner.close();
    }
}

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