Submission #1148090

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

joi2019_ho_t4

import java.util.*;
import static java.lang.Math.*;

public class Main {

  static int clamp(int value, int min, int max) {
    if (value < min) return min;
    if (value > max) return max;
    return value;
  }

  static long adjustmentCost(int c, int r, int maxCol) {
    long cost = 0;
    if (r < 1) cost += (1 - r);
    if (r > 2) cost += (r - 2);
    if (c < 1) cost += (1 - c);
    if (c > maxCol) cost += (c - maxCol);
    return cost;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int totalCoins = 2 * n;

    int[] coinsRow1 = new int[n + 1];
    int[] coinsRow2 = new int[n + 1];
    long clampCost = 0;

    for (int i = 0; i < totalCoins; i++) {
      int c = sc.nextInt();
      int r = sc.nextInt();
      clampCost += adjustmentCost(c, r, n);
      int validC = clamp(c, 1, n);
      int validR = clamp(r, 1, 2);
      if (validR == 1)
        coinsRow1[validC]++;
      else
        coinsRow2[validC]++;
    }

    int[] X = new int[n + 1];
    int[] Y = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      X[i] = coinsRow1[i] - 1;
      Y[i] = coinsRow2[i] - 1;
    }

    int[] S1 = new int[n + 1];
    int[] S2 = new int[n + 1];
    S1[0] = 0; S2[0] = 0;
    for (int i = 1; i <= n; i++) {
      S1[i] = S1[i - 1] + X[i];
      S2[i] = S2[i - 1] + Y[i];
    }

    int deltaMin = -100, deltaMax = 100;
    List<Map<Integer, Long>> dp = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
      dp.add(new HashMap<>());
    }

    for (int d = deltaMin; d <= deltaMax; d++) {
      long cost = abs(S1[1] - d) + abs(S2[1] + d) + abs(d);
      dp.get(1).put(d, cost);
    }

    for (int i = 2; i <= n - 1; i++) {
      Map<Integer, Long> prev = dp.get(i - 1);
      Map<Integer, Long> cur = dp.get(i);
      for (int dPrev = deltaMin; dPrev <= deltaMax; dPrev++) {
        if (!prev.containsKey(dPrev)) continue;
        long prevCost = prev.get(dPrev);
        for (int d = deltaMin; d <= deltaMax; d++) {
          long horiz = abs(d - dPrev);
          long balance = abs(S1[i] - d) + abs(S2[i] + d);
          long candidate = prevCost + horiz + balance;
          if (!cur.containsKey(d) || candidate < cur.get(d)) {
            cur.put(d, candidate);
          }
        }
      }
    }

    long finalCost = Long.MAX_VALUE;
    Map<Integer, Long> prev = dp.get(n - 1);
    for (int dPrev = deltaMin; dPrev <= deltaMax; dPrev++) {
      if (!prev.containsKey(dPrev)) continue;
      long candidate = prev.get(dPrev) + abs(S1[n] - dPrev);
      finalCost = min(finalCost, candidate);
    }

    long answer = clampCost + finalCost;
    System.out.println(answer);
  }
}

Compilation message (stderr)

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

=======