#1144897 (Java) No.705 ゴミ拾い Hard

• 問題: No.705 ゴミ拾い Hard
• ユーザー: 37zigen
• 提出日時: 2026-01-16 01:14:42
• 言語: Java (openjdk 25.0.1)
• 結果: AC
• 実行時間: 322 ms / 1,500 ms
• コード長: 7,158 bytes
• コンパイル時間: 2,944 ms
• コンパイル使用メモリ: 103,136 KB
• 実行使用メモリ: 58,980 KB
• 最終ジャッジ日時: 2026-01-16 01:14:55
• 合計ジャッジ時間: 11,887 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 4
other	AC * 40

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.nio.file.Files;
import java.nio.file.OpenOption;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Optional;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.random.RandomGenerator;
import java.util.stream.Stream;

class FastScanner {
    private static FastScanner instance = null;

    private final InputStream in = System.in;

    private final byte[] buffer = new byte[1024];

    private int ptr = 0;

    private int buflen = 0;

    private FastScanner() {
    }

    public static FastScanner getInstance() {
        if (instance == null) {
            instance = new FastScanner();
        }
        return instance;
    }

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }
        ptr = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return buflen > 0;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private boolean isPrintableChar(int c) {
        return (33 <= c) && (c <= 126);
    }

    public boolean hasNext() {
        while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
            ptr++;
        } 
        return hasNextByte();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while ((b >= '0') && (b <= '9')) {
            // n = n * 10 + (b - '0');
            n = ((n << 1) + (n << 3)) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }

    public int nextInt() {
        return ((int) (nextLong()));
    }

    public long[] nextLongs(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; ++i) {
            a[i] = nextLong();
        }
        return a;
    }
}

class Intervals {
    /**
     * c:=f.costがMongeと仮定して
     * d[0]=0
     * d[i]=min_{k < i} d[k]+c(k, i)
     * を計算してd[n]を返す。
     *
     * @param f
     * @param n
     * @return  * @see https://yukicoder.me/submissions/1144894
     * @see Galil, Zvi, and Raffaele Giancarlo. "Speeding up dynamic programming with applications to molecular biology." Theoretical Computer Science 64.1 (1989): 107-118.
     */
    public static long minPartitionOfMongeCost(Cost f, int n) {
        long[] d = new long[n + 1];
        // g(k, i) := d[k]+c(k , i) とすると
        // k < l の下で g(k, x) - g(l, x) は x の単調増加関数。
        // なぜなら
        // c(k, x) - c(l, x) ≤ c(k, x+1) - c(l, x+1)
        // ⇔ c(k, x) + c(l, x+1)  ≤ c(l, x) + c(k, x+1) -
        // が Monge の定義より成り立つから。
        // 従って、lower envelope を管理する CHT と同様の構造を持つ。
        int[][] deque = new int[2][n];// 交点のx座標のceil, 交点の左側を担当する g(k, i) の k

        int s = 0;
        int t = 1;
        int INFX = n + 1;
        deque[0][0] = INFX;// 右側に直線がない場合、右側の交点のx座標は∞と置く。

        for (int i = 1; i <= n; i++) {
            while (deque[0][s] <= i) {
                s++;
            } 
            d[i] = d[deque[1][s]] + f.cost(deque[1][s], i);
            if (i == n) {
                break;
            }
            do {
                int ok = n + 1;
                int ng = i;
                while (Math.abs(ok - ng) != 1) {
                    int mid = (ok + ng) / 2;
                    if ((d[deque[1][t - 1]] + f.cost(deque[1][t - 1], mid)) >= (d[i] + f.cost(i, mid))) {
                        ok = mid;
                    } else {
                        ng = mid;
                    }
                } 
                if (((t - s) >= 2) && (ok <= deque[0][t - 2])) {
                    t--;
                } else {
                    deque[0][t - 1] = ok;
                    deque[0][t] = INFX;
                    deque[1][t] = i;
                    t++;
                    break;
                }
            } while (true );
        }
        return d[n];
    }

    interface Cost {
        public long cost(int i, int j);
    }
}

class MergeFiles {}

class MyPrintWriter extends PrintWriter {
    private static MyPrintWriter instance = null;

    private MyPrintWriter() {
        super(System.out);
    }

    public static MyPrintWriter getInstance() {
        if (instance == null) {
            instance = new MyPrintWriter();
        }
        return instance;
    }

    public void println(boolean[][] a) {
        for (int i = 0; i < a.length; i++) {
            println(a[i], " ");
        }
    }

    public void println(boolean[] a, String separator) {
        for (int i = 0; i < a.length; ++i) {
            super.print((a[i] ? 1 : 0) + (i == (a.length - 1) ? "\n" : separator));
        }
    }
}

public class Main implements Runnable {
    public static void main(String[] args) throws IOException {
        Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
        // Runtime runtime = Runtime.getRuntime();
        // new Thread(null, new Main(), "MainThreadWithLargeStack", (1024 * 1024) * 1024).start();
        // new Main().test();
        // new Main().gen();
        new Main().run();
        // new Main().solve();
        // long usedMemory = runtime.totalMemory() - runtime.freeMemory();
        // System.err.printf("使用メモリ: %.2f MB%n", usedMemory / 1024.0 / 1024.0);
        MyPrintWriter.getInstance().flush();
    }

    @Override
    public void run() {
        FastScanner sc = FastScanner.getInstance();
        MyPrintWriter pw = MyPrintWriter.getInstance();
        int N = sc.nextInt();
        long[] A = sc.nextLongs(N);
        long[] X = sc.nextLongs(N);
        long[] Y = sc.nextLongs(N);
        var f = new Intervals.Cost() {
            @Override
            public long cost(int i, int j) {
                long dx = A[j - 1] - X[i];
                long dy = 0 - Y[i];
                dx = Math.abs(dx);
                dy = Math.abs(dy);
                return ((dx * dx) * dx) + ((dy * dy) * dy);
            }
        };
        pw.println(Intervals.minPartitionOfMongeCost(f, N));
        pw.flush();
    }
}