Submission #1146225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146225		lucianaft	Coin Collecting (JOI19_ho_t4)	Java	Compilation error	0 ms	0 KiB

joi2019_ho_t4

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
  static class Point {
    int x, y;
    Point(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }

  static class State {
    int x, y, dist;
    State(int x, int y, int dist) {
      this.x = x;
      this.y = y;
      this.dist = dist;
    }
  }

  private static int getManhattanDistance(Point a, Point b) {
    return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
  }

  private static int hungarianAlgorithm(int[][] costMatrix, int n) {
    int[] u = new int[n];
    int[] v = new int[n];
    int[] p = new int[n];
    int[] way = new int[n];

    for (int i = 1; i < n; i++) {
      p[0] = i;
      int j0 = 0;
      int[] minv = new int[n];
      Arrays.fill(minv, Integer.MAX_VALUE);
      boolean[] used = new boolean[n];

      do {
        used[j0] = true;
        int i0 = p[j0];
        int delta = Integer.MAX_VALUE;
        int j1 = 0;

        for (int j = 1; j < n; j++) {
          if (!used[j]) {
            int cur = costMatrix[i0][j] - u[i0] - v[j];
            if (cur < minv[j]) {
              minv[j] = cur;
              way[j] = j0;
            }
            if (minv[j] < delta) {
              delta = minv[j];
              j1 = j;
            }
          }
        }

        for (int j = 0; j < n; j++) {
          if (used[j]) {
            u[p[j]] += delta;
            v[j] -= delta;
          } else {
            minv[j] -= delta;
          }
        }

        j0 = j1;

      } while (p[j0] != 0);

      do {
        int j1 = way[j0];
        p[j0] = p[j1];
        j0 = j1;
      } while (j0 != 0);
    }

    int result = 0;
    for (int j = 0; j < n; j++) {
      result += costMatrix[p[j]][j];
    }
    return result;
  }

  public static int minMoves(int N, Point[] coins) {
    Point[] targets = new Point[2 * N];
    int idx = 0;
    for (int x = 1; x <= N; x++) {
      for (int y = 1; y <= 2; y++) {
        targets[idx++] = new Point(x, y);
      }
    }

    int[][] costMatrix = new int[2 * N][2 * N];
    for (int i = 0; i < 2 * N; i++) {
      for (int j = 0; j < 2 * N; j++) {
        costMatrix[i][j] = getManhattanDistance(coins[i], targets[j]);
      }
    }

    return hungarianAlgorithm(costMatrix, 2 * N);
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine().trim());
    Point[] coins = new Point[2 * N];

    for (int i = 0; i < 2 * N; i++) {
      String[] line = br.readLine().trim().split(" ");
      int x = Integer.parseInt(line[0]);
      int y = Integer.parseInt(line[1]);
      coins[i] = new Point(x, y);
    }

    System.out.println(minMoves(N, coins));
  }
}

Compilation message (stderr)

joi2019_ho_t4.java:7: error: class Main is public, should be declared in a file named Main.java
public class Main {
       ^
1 error

=======