제출 #1145534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145534		machaca_rodrigo	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	76 ms	12632 KiB

joi2019_ho_t4

import java.util.*;
public class joi2019_ho_t4 {
    static class Coin implements Comparable<Coin> {
        long x, y;
        Coin(long x, long y) {
            this.x = x; this.y = y;
        }
        public int compareTo(Coin o) {
            return Long.compare(this.x, o.x);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int total = 2 * n;
        Coin[] coins = new Coin[total];
        long extraCost = 0;
        for (int i = 0; i < total; i++) {
            long cx = sc.nextLong(), cy = sc.nextLong();
            if(cx < 1) { extraCost += (1 - cx); cx = 1; }
            if(cx > n) { extraCost += (cx - n); cx = n; }
            if(cy < 1) { extraCost += (1 - cy); cy = 1; }
            if(cy > 2) { extraCost += (cy - 2); cy = 2; }
            coins[i] = new Coin(cx, cy);
        }
        Arrays.sort(coins);
        long costX = 0;
        for (int i = 0; i < total; i++) {
            long target = (i / 2) + 1;
            costX += Math.abs(coins[i].x - target);
        }

        long INF = Long.MAX_VALUE / 2;
        long[] dp = new long[n + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int i = 0; i < total; i++) {
            long costRow1 = (coins[i].y == 1 ? 0 : 1);
            long costRow2 = (coins[i].y == 2 ? 0 : 1);
            long[] newdp = new long[n + 1];
            Arrays.fill(newdp, INF);
            for (int j = 0; j <= n; j++) {
                if (dp[j] < INF) {
                    // Asignar a fila 2 (no incrementa el contador de fila1)
                    newdp[j] = Math.min(newdp[j], dp[j] + costRow2);
                    // Asignar a fila 1 (incrementa contador)
                    if(j + 1 <= n)
                        newdp[j + 1] = Math.min(newdp[j + 1], dp[j] + costRow1);
                }
            }
            dp = newdp;
        }
        long costY = dp[n];
        System.out.println(extraCost + costX + costY);
        sc.close();
    }
}

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