Submission #1148147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148147		ruben_ipenza	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	75 ms	12608 KiB

joi2019_ho_t4

import java.util.*;

class joi2019_ho_t4 {

    public static int minStepsRecur(int[] coinsX, int[] coinsY, int[] targetX, int[] targetY, int l, int r) {
        if (l >= r) return 0;

        int m = l;
        for (int i = l; i < r; i++) {
            if (coinsX[i] < coinsX[m]) {
                m = i;
            }
        }
        return Math.min(r - l,
                minStepsRecur(coinsX, coinsY, targetX, targetY, l, m) +
                        minStepsRecur(coinsX, coinsY, targetX, targetY, m + 1, r) +
                        Math.abs(coinsX[m] - targetX[m]) + Math.abs(coinsY[m] - targetY[m]));
    }

    public static int minSteps(int[] coinsX, int[] coinsY, int N) {
        int[] targetX = new int[N];
        int[] targetY = new int[2 * N];

        // Generamos las posiciones de destino de las monedas
        for (int i = 0; i < N; i++) {
            targetX[i] = i + 1;  // Las posiciones en X son 1..N
            targetY[i] = 1;      // La primera columna de destino
            targetY[N + i] = 2;  // La segunda columna de destino
        }

        return minStepsRecur(coinsX, coinsY, targetX, targetY, 0, N);
    }

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

        int N = sc.nextInt();

        int[] coinsX = new int[2 * N];
        int[] coinsY = new int[2 * N];

        for (int i = 0; i < 2 * N; i++) {
            coinsX[i] = sc.nextInt();
            coinsY[i] = sc.nextInt();
        }

        System.out.println(minSteps(coinsX, coinsY, N));
        sc.close();
    }
}

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