제출 #1147993

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

joi2019_ho_t4

import java.util.*;

class Coin implements Comparable<Coin> {
  int X, Y;
  public Coin(int X, int Y) {
    this.X = X;
    this.Y = Y;
  }
  public int compareTo(Coin other) {
    return Integer.compare(this.X, other.X);
  }
}

public class joi2019_ho_t4 {
  
  static final long INF = Long.MAX_VALUE / 2;

  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];
    for (int i = 0; i < total; i++) {
      int X = sc.nextInt();
      int Y = sc.nextInt();
      coins[i] = new Coin(X, Y);
    }
    Arrays.sort(coins);

    long costoHorizontal = 0;
    for (int i = 0; i < total; i++) {
      int destinoX = (i / 2) + 1;
      costoHorizontal += Math.abs(coins[i].X - destinoX);
    }

    long[][] dp = new long[total + 1][N + 1];
    for (int i = 0; i <= total; i++) {
      Arrays.fill(dp[i], INF);
    }
    dp[0][0] = 0;

    for (int i = 1; i <= total; i++) {
      for (int j = Math.max(0, i - N); j <= Math.min(i, N); j++) {
        if (j > 0) {
          dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1] + Math.abs(coins[i-1].Y - 1));
        }
        if ((i - j) > 0 && (i - j) <= N) {
          dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + Math.abs(coins[i-1].Y - 2));
        }
      }
    }

    long costoVertical = dp[total][N];
    long respuestaTotal = costoHorizontal + costoVertical;
    System.out.println(respuestaTotal);
  }
}

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