結果
| 問題 |
No.409 ダイエット
|
| コンテスト | |
| ユーザー |
 tutuz
|
| 提出日時 | 2019-02-18 16:12:13 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,191 bytes |
| コンパイル時間 | 2,391 ms |
| コンパイル使用メモリ | 80,488 KB |
| 実行使用メモリ | 50,652 KB |
| 最終ジャッジ日時 | 2024-10-07 00:00:35 |
| 合計ジャッジ時間 | 15,498 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 82 WA * 10 |
ソースコード
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
MyInput in = new MyInput(inputStream);
PrintWriter out = new PrintWriter(outputStream);
TaskX solver = new TaskX();
solver.solve(1, in, out);
out.close();
}
static int INF = 1 << 30;
static long LINF = 1L << 55;
static int MOD = 1000000007;
static int[] mh4 = { 0, -1, 1, 0 };
static int[] mw4 = { -1, 0, 0, 1 };
static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };
static class TaskX {
public void solve(int testNumber, MyInput in, PrintWriter out) {
int n = in.nextInt();
long a = in.nextLong(), b = in.nextLong(), w = in.nextLong();
long[] d = in.nextLongArray(n);
ConvexHullTrick cht = new ConvexHullTrick(n + 100);
long[] dp = new long[n+1];
dp[0] = 0;
for (int i = 1; i < n+1; i++) {
dp[i] = cht.query(i-1) - (i-1) * a + (long)(i-1) * i / 2 * b + d[i-1];
cht.addLine(-i * b, dp[i] + i * a + (long)(i - 1) * i / 2 * b);
}
long ans = LINF;
for (int i = 0; i < n+1; i++) {
ans = Math.min(ans, dp[i] - (n - i) * a + (long)(n - i) * (n - i + 1) / 2 * b);
}
out.println(w + ans);
}
/**
* 追加クエリの直線の傾きが単調減少の場合
* - insert (a, b): add y = ax + b
* - query (x) : min_i{a[i]x + b}
* */
class ConvexHullTrick {
long[] A, B;
int len;
public ConvexHullTrick(int n) {
A = new long[n];
B = new long[n];
}
private boolean check(long a, long b) {
return (B[len - 2] - B[len - 1]) * (a - A[len - 1]) >= (B[len - 1] - b) * (A[len - 1] - A[len - 2]);
}
public void addLine(long a, long b) {
while (len >= 2 && check(a, b)) {
len--;
}
A[len] = a;
B[len] = b;
len++;
}
public long query(long x) {
int l = -1, r = len;
while (r - l > 1) {
int mid = (r + l) / 2;
if (get(mid, x) >= get(mid + 1, x)) {
l = mid;
} else {
r = mid;
}
}
return get(r, x);
}
private long get(int k, long x) {
return A[k] * x + B[k];
}
}
}
static class MyInput {
private final BufferedReader in;
private static int pos;
private static int readLen;
private static final char[] buffer = new char[1024 * 8];
private static char[] str = new char[500 * 8 * 2];
private static boolean[] isDigit = new boolean[256];
private static boolean[] isSpace = new boolean[256];
private static boolean[] isLineSep = new boolean[256];
static {
for (int i = 0; i < 10; i++) {
isDigit['0' + i] = true;
}
isDigit['-'] = true;
isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
isLineSep['\r'] = isLineSep['\n'] = true;
}
public MyInput(InputStream is) {
in = new BufferedReader(new InputStreamReader(is));
}
public int read() {
if (pos >= readLen) {
pos = 0;
try {
readLen = in.read(buffer);
} catch (IOException e) {
throw new RuntimeException();
}
if (readLen <= 0) {
throw new MyInput.EndOfFileRuntimeException();
}
}
return buffer[pos++];
}
public int nextInt() {
int len = 0;
str[len++] = nextChar();
len = reads(len, isSpace);
int i = 0;
int ret = 0;
if (str[0] == '-') {
i = 1;
}
for (; i < len; i++)
ret = ret * 10 + str[i] - '0';
if (str[0] == '-') {
ret = -ret;
}
return ret;
}
public long nextLong() {
int len = 0;
str[len++] = nextChar();
len = reads(len, isSpace);
int i = 0;
long ret = 0;
if (str[0] == '-') {
i = 1;
}
for (; i < len; i++)
ret = ret * 10 + str[i] - '0';
if (str[0] == '-') {
ret = -ret;
}
return ret;
}
public char nextChar() {
while (true) {
final int c = read();
if (!isSpace[c]) {
return (char) c;
}
}
}
public String nextString() {
return new String(nextChars());
}
public char[] nextChars() {
int len = 0;
str[len++] = nextChar();
len = reads(len, isSpace);
return Arrays.copyOf(str, len);
}
public char[][] next2DChars(int h, int w) {
char[][] s = new char[h][w];
for (int i = 0; i < h; i++) {
s[i] = nextChars();
}
return s;
}
int reads(int len, boolean[] accept) {
try {
while (true) {
final int c = read();
if (accept[c]) {
break;
}
if (str.length == len) {
char[] rep = new char[str.length * 3 / 2];
System.arraycopy(str, 0, rep, 0, str.length);
str = rep;
}
str[len++] = (char) c;
}
} catch (MyInput.EndOfFileRuntimeException e) {
}
return len;
}
public int[] nextIntArray(final int n) {
final int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}
public int[] nextIntArray1Index(final int n) {
final int[] res = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
res[i] = nextInt();
}
return res;
}
public int[] nextIntArrayDec(final int n) {
final int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt() - 1;
}
return res;
}
public long[] nextLongArray(final int n) {
final long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong();
}
return res;
}
public long[] nextLongArray1Index(final int n) {
final long[] res = new long[n + 1];
for (int i = 1; i < n + 1; i++) {
res[i] = nextLong();
}
return res;
}
public long[] nextLongArrayDec(final int n) {
final long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong() - 1;
}
return res;
}
public double nextDouble() {
return Double.parseDouble(nextString());
}
public double[] nextDoubleArray(int n) {
double[] res = new double[n];
for (int i = 0; i < n; i++) {
res[i] = nextDouble();
}
return res;
}
static class EndOfFileRuntimeException extends RuntimeException {
}
}
}