Submission #1147681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147681		mendoza_gabriel	Coin Collecting (JOI19_ho_t4)	Java	37 / 100	1102 ms	166396 KiB

joi2019_ho_t4

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;


public class joi2019_ho_t4 {
    static final long INF = 1000000000000000000L;
    static int totalCoins;
    static int[] coinX;
    static int[] coinY;
    static int[] auxX;
    static int[] auxY;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = parseInt(br.readLine().trim());
        totalCoins = 2 * N;
        coinX = new int[totalCoins + 1];
        coinY = new int[totalCoins + 1];
        for (int i = 1; i <= totalCoins; i++) {
            String[] parts = mySplit(br.readLine());
            coinX[i] = parseInt(parts[0]);
            coinY[i] = parseInt(parts[1]);
        }
        auxX = new int[totalCoins + 1];
        auxY = new int[totalCoins + 1];
        mergeSort(1, totalCoins);
        long[] dp = new long[N + 1];
        for (int j = 0; j <= N; j++) dp[j] = INF;
        dp[0] = 0;
        for (int i = 1; i <= totalCoins; i++) {
            long[] ndp = new long[N + 1];
            for (int j = 0; j <= N; j++) ndp[j] = INF;
            for (int j = 0; j <= Math.min(i - 1, N); j++) {
                if (dp[j] == INF) continue;
                int cntRow2 = (i - 1) - j;
                if (j < N) {
                    int targetX1 = j + 1;
                    long cost1 = abs(coinX[i] - targetX1) + abs(coinY[i] - 1);
                    if (dp[j] + cost1 < ndp[j + 1]) ndp[j + 1] = dp[j] + cost1;
                }
                if (cntRow2 < N) {
                    int targetX2 = cntRow2 + 1;
                    long cost2 = abs(coinX[i] - targetX2) + abs(coinY[i] - 2);
                    if (dp[j] + cost2 < ndp[j]) ndp[j] = dp[j] + cost2;
                }
            }
            dp = ndp;
        }
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        out.println(dp[N]);
        out.flush();
    }
    static void mergeSort(int l, int r) {
        if(l >= r) return;
        int m = (l + r) / 2;
        mergeSort(l, m);
        mergeSort(m+1, r);
        int i = l, j = m+1, k = l;
        while(i <= m && j <= r) {
            if(coinX[i] < coinX[j] || (coinX[i] == coinX[j] && coinY[i] <= coinY[j])) {
                auxX[k] = coinX[i];
                auxY[k] = coinY[i];
                i++;
            } else {
                auxX[k] = coinX[j];
                auxY[k] = coinY[j];
                j++;
            }
            k++;
        }
        while(i <= m) { auxX[k] = coinX[i]; auxY[k] = coinY[i]; i++; k++; }
        while(j <= r) { auxX[k] = coinX[j]; auxY[k] = coinY[j]; j++; k++; }
        for (i = l; i <= r; i++) {
            coinX[i] = auxX[i];
            coinY[i] = auxY[i];
        }
    }
    static int abs(int a) { return a < 0 ? -a : a; }
    static String[] mySplit(String s) {
        int len = s.length(), cnt = 0;
        boolean inToken = false;
        for (int i = 0; i < len; i++) {
            if (!isSpace(s.charAt(i))) { if (!inToken) { cnt++; inToken = true; } }
            else { inToken = false; }
        }
        String[] tokens = new String[cnt];
        int index = 0;
        StringBuilder sb = new StringBuilder();
        inToken = false;
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (!isSpace(c)) { sb.append(c); inToken = true; }
            else { if (inToken) { tokens[index++] = sb.toString(); sb.setLength(0); inToken = false; } }
        }
        if (inToken) tokens[index++] = sb.toString();
        return tokens;
    }
    static boolean isSpace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }
    static int parseInt(String s) {
        int i = 0, n = s.length(), num = 0, sign = 1;
        if(n == 0)return 0;
        char c = s.charAt(0);
        if(c == '-') { sign = -1; i++; } else if(c == '+') { i++; }
        for(; i < n; i++){
            num = num * 10 + (s.charAt(i) - '0');
        }
        return sign * num;
    }
}

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