Submission #1148116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148116		lucianaft	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	79 ms	13124 KiB

joi2019_ho_t4

import java.util.Scanner;

public class joi2019_ho_t4 {
  
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in); 
    int numberOfRows = scanner.nextInt(); 
    long[][] coinCoordinates = new long[2 * numberOfRows][2]; 

    for (int index = 0; index < 2 * numberOfRows; index++) {
      coinCoordinates[index][0] = scanner.nextLong(); 
      coinCoordinates[index][1] = scanner.nextLong(); 
    }

    System.out.println(calculateMinimumMoves(numberOfRows, coinCoordinates)); 
    scanner.close(); 
  }
  
  public static long calculateMinimumMoves(int numberOfRows, long[][] coinCoordinates) {
    Position[] coinPositions = new Position[2 * numberOfRows]; 
    Position[] targetPositions = new Position[2 * numberOfRows]; 

    for (int index = 0; index < 2 * numberOfRows; index++) {
      coinPositions[index] = new Position(coinCoordinates[index][0], coinCoordinates[index][1]); 
    }

    int targetIndex = 0; 
    for (int row = 1; row <= numberOfRows; row++) {
      targetPositions[targetIndex++] = new Position(row, 1); 
      targetPositions[targetIndex++] = new Position(row, 2); 
    }

    boolean[] isTargetUsed = new boolean[2 * numberOfRows]; 
    long totalDistance = 0; 

    for (int coinIndex = 0; coinIndex < 2 * numberOfRows; coinIndex++) {
      long minimumDistance = Long.MAX_VALUE;
      int optimalTargetIndex = -1; 

      for (int targetIndexInner = 0; targetIndexInner < 2 * numberOfRows; targetIndexInner++) {
        if (!isTargetUsed[targetIndexInner]) { 
          long currentDistance = calculateManhattanDistance(coinPositions[coinIndex], targetPositions[targetIndexInner]); 
          if (currentDistance < minimumDistance) { 
            minimumDistance = currentDistance; 
            optimalTargetIndex = targetIndexInner; 
          }
        }
      }

      isTargetUsed[optimalTargetIndex] = true; 
      totalDistance += minimumDistance; 
    }

    return totalDistance; 
  }
  
  public static long calculateManhattanDistance(Position from, Position to) {
    return Math.abs(from.x - to.x) + Math.abs(from.y - to.y); 
  }

  static class Position {
    long x;
    long y;

    Position(long x, long y) {
      this.x = x;
      this.y = y;
    }
  }
}

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