結果
問題 | No.409 ダイエット |
ユーザー |
![]() |
提出日時 | 2016-08-13 07:51:09 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 279 ms / 2,000 ms |
コード長 | 6,093 bytes |
コンパイル時間 | 4,016 ms |
コンパイル使用メモリ | 80,536 KB |
実行使用メモリ | 56,936 KB |
最終ジャッジ日時 | 2024-06-26 09:53:18 |
合計ジャッジ時間 | 18,579 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 92 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.OutputStream;import java.io.PrintWriter;import java.util.ArrayList;import java.util.Arrays;import java.util.NoSuchElementException;/*_ooOoo_o8888888o88" . "88(| -_- |)O\ = /O____/`---'\____.' \\| |// `./ \\||| : |||// \/ _||||| -:- |||||- \| | \\\ - /// | || \_| ''\---/'' | |\ .-\__ `-` ___/-. /___`. .' /--.--\ `. . __."" '< `.___\_<|>_/___.' >'"".| | : `- \`.;`\ _ /`;.`/ - ` : | |\ \ `-. \_ __\ /__ _/ .-` / /======`-.____`-.___\_____/___.-`____.-'======`=---='^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^pass System Test!*/public class yukicoder409 {private static class Task {class ConvexHullTrick {ArrayList<long[]> ls = new ArrayList<>();ConvexHullTrick() {}boolean check(long[] l1, long[] l2, long[] l3) {return (l2[0] - l1[0]) * (l3[1] - l2[1]) >=(l2[1] - l1[1]) * (l3[0] - l2[0]);}void add(long a, long b) {long[] l = new long[]{a, b};while (ls.size() >= 2 && check(ls.get(ls.size() - 2), ls.get(ls.size() - 1), l)) ls.remove(ls.size() - 1);ls.add(l);}long f(int k, long x) {long[] l = ls.get(k);return l[0] * x + l[1];}long query(long x) {int low = -1;int high = ls.size() - 1;while (high - low > 1) {int mid = (high + low) / 2;if (f(mid, x) >= f(mid + 1, x)) {low = mid;} else {high = mid;}}return f(high, x);}}final long INF = (long) 1e18;void solve(FastScanner in, PrintWriter out) {int N = in.nextInt();int A = in.nextInt();long B = in.nextInt();int W = in.nextInt();int[] D = in.nextIntArray(N);if (B == 0) {out.println(W - A * N);return;}long[] dp = new long[N + 1];Arrays.fill(dp, INF);dp[0] = W;ConvexHullTrick deq = new ConvexHullTrick();deq.add(0, dp[0]);for (long i = 0; i < N; i++) {dp[(int) i + 1] = D[(int) i] - i * A + (B * i * (i + 1)) / 2 + deq.query(i);long a = -(i + 1) * B;long b = dp[(int) i + 1] + (i + 1) * A + (B * (i + 1) * i) / 2;deq.add(a, b);}long res = INF;for (int i = 0; i <= N; i++)res = Math.min(res, dp[i] - A * (N - i) + B * (N - i) * (N - i + 1) / 2);out.println(res);}}/*** ここから下はテンプレートです。*/public static void main(String[] args) {OutputStream outputStream = System.out;FastScanner in = new FastScanner();PrintWriter out = new PrintWriter(outputStream);Task solver = new Task();solver.solve(in, out);out.close();}private static class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int bufferLength = 0;private boolean hasNextByte() {if (ptr < bufferLength) {return true;} else {ptr = 0;try {bufferLength = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (bufferLength <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte()) return buffer[ptr++];else return -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}private void skipUnprintable() {while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}boolean hasNext() {skipUnprintable();return hasNextByte();}public String next() {if (!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}long nextLong() {if (!hasNext()) throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while (true) {if ('0' <= b && b <= '9') {n *= 10;n += b - '0';} else if (b == -1 || !isPrintableChar(b)) {return minus ? -n : n;} else {throw new NumberFormatException();}b = readByte();}}double nextDouble() {return Double.parseDouble(next());}double[] nextDoubleArray(int n) {double[] array = new double[n];for (int i = 0; i < n; i++) {array[i] = nextDouble();}return array;}double[][] nextDoubleMap(int n, int m) {double[][] map = new double[n][];for (int i = 0; i < n; i++) {map[i] = nextDoubleArray(m);}return map;}public int nextInt() {return (int) nextLong();}public int[] nextIntArray(int n) {int[] array = new int[n];for (int i = 0; i < n; i++) array[i] = nextInt();return array;}public long[] nextLongArray(int n) {long[] array = new long[n];for (int i = 0; i < n; i++) array[i] = nextLong();return array;}public String[] nextStringArray(int n) {String[] array = new String[n];for (int i = 0; i < n; i++) array[i] = next();return array;}public char[][] nextCharMap(int n) {char[][] array = new char[n][];for (int i = 0; i < n; i++) array[i] = next().toCharArray();return array;}}}