結果

問題 No.409 ダイエット
ユーザー uwiuwi
提出日時 2016-08-06 01:02:56
言語 Java21
(openjdk 21)
結果
AC  
実行時間 159 ms / 2,000 ms
コード長 3,996 bytes
コンパイル時間 7,402 ms
コンパイル使用メモリ 84,924 KB
実行使用メモリ 47,200 KB
最終ジャッジ日時 2024-06-26 09:45:39
合計ジャッジ時間 15,828 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
36,576 KB
testcase_01 AC 49 ms
37,044 KB
testcase_02 AC 52 ms
37,144 KB
testcase_03 AC 49 ms
37,188 KB
testcase_04 AC 49 ms
36,580 KB
testcase_05 AC 50 ms
36,864 KB
testcase_06 AC 50 ms
37,188 KB
testcase_07 AC 51 ms
37,188 KB
testcase_08 AC 50 ms
36,972 KB
testcase_09 AC 50 ms
36,744 KB
testcase_10 AC 49 ms
36,916 KB
testcase_11 AC 48 ms
37,180 KB
testcase_12 AC 53 ms
37,080 KB
testcase_13 AC 50 ms
37,140 KB
testcase_14 AC 51 ms
37,188 KB
testcase_15 AC 50 ms
37,164 KB
testcase_16 AC 49 ms
37,188 KB
testcase_17 AC 51 ms
37,188 KB
testcase_18 AC 49 ms
37,160 KB
testcase_19 AC 52 ms
36,928 KB
testcase_20 AC 51 ms
37,188 KB
testcase_21 AC 50 ms
36,596 KB
testcase_22 AC 49 ms
37,304 KB
testcase_23 AC 50 ms
37,188 KB
testcase_24 AC 50 ms
37,056 KB
testcase_25 AC 48 ms
37,148 KB
testcase_26 AC 51 ms
37,188 KB
testcase_27 AC 50 ms
37,068 KB
testcase_28 AC 51 ms
36,876 KB
testcase_29 AC 49 ms
36,956 KB
testcase_30 AC 49 ms
37,068 KB
testcase_31 AC 49 ms
37,120 KB
testcase_32 AC 50 ms
36,900 KB
testcase_33 AC 51 ms
36,796 KB
testcase_34 AC 51 ms
36,884 KB
testcase_35 AC 53 ms
37,100 KB
testcase_36 AC 53 ms
37,272 KB
testcase_37 AC 54 ms
37,316 KB
testcase_38 AC 54 ms
37,316 KB
testcase_39 AC 52 ms
37,044 KB
testcase_40 AC 53 ms
37,320 KB
testcase_41 AC 53 ms
37,056 KB
testcase_42 AC 53 ms
37,180 KB
testcase_43 AC 52 ms
37,316 KB
testcase_44 AC 54 ms
36,872 KB
testcase_45 AC 54 ms
36,752 KB
testcase_46 AC 53 ms
36,872 KB
testcase_47 AC 53 ms
36,616 KB
testcase_48 AC 53 ms
37,268 KB
testcase_49 AC 56 ms
37,044 KB
testcase_50 AC 55 ms
36,744 KB
testcase_51 AC 52 ms
37,088 KB
testcase_52 AC 54 ms
36,752 KB
testcase_53 AC 54 ms
37,056 KB
testcase_54 AC 53 ms
37,072 KB
testcase_55 AC 123 ms
44,248 KB
testcase_56 AC 95 ms
42,172 KB
testcase_57 AC 152 ms
47,200 KB
testcase_58 AC 126 ms
42,068 KB
testcase_59 AC 151 ms
45,320 KB
testcase_60 AC 115 ms
41,924 KB
testcase_61 AC 152 ms
46,052 KB
testcase_62 AC 143 ms
46,400 KB
testcase_63 AC 142 ms
45,628 KB
testcase_64 AC 127 ms
44,080 KB
testcase_65 AC 154 ms
46,316 KB
testcase_66 AC 153 ms
46,652 KB
testcase_67 AC 139 ms
45,264 KB
testcase_68 AC 137 ms
45,500 KB
testcase_69 AC 139 ms
45,616 KB
testcase_70 AC 145 ms
45,480 KB
testcase_71 AC 131 ms
43,952 KB
testcase_72 AC 147 ms
46,808 KB
testcase_73 AC 144 ms
46,164 KB
testcase_74 AC 138 ms
44,668 KB
testcase_75 AC 155 ms
46,360 KB
testcase_76 AC 142 ms
44,328 KB
testcase_77 AC 151 ms
41,976 KB
testcase_78 AC 133 ms
44,436 KB
testcase_79 AC 124 ms
41,696 KB
testcase_80 AC 159 ms
46,340 KB
testcase_81 AC 147 ms
46,136 KB
testcase_82 AC 140 ms
44,624 KB
testcase_83 AC 151 ms
45,020 KB
testcase_84 AC 138 ms
45,192 KB
testcase_85 AC 80 ms
38,852 KB
testcase_86 AC 134 ms
44,796 KB
testcase_87 AC 151 ms
45,320 KB
testcase_88 AC 122 ms
41,080 KB
testcase_89 AC 155 ms
44,560 KB
testcase_90 AC 122 ms
41,440 KB
testcase_91 AC 157 ms
44,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package contest;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class N409 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni();
long a = ni(), b = ni(), w = ni();
int[] d = Arrays.copyOf(na(n), n+1);
long[] dp = new long[n+2];
dp[0] = w;
// dp+b(x-t)(x-t-1)/2-a(x-t)
// b/2*x^2+x((-bt-bt+b)/2-a)+dp+bt(t+1)/2+at
if(b == 0){
out.println(w-(long)a*n);
return;
}
int[] q = new int[n+2];
long[] qw = new long[n+2];
int qp = 0;
for(int i = 1;i <= n+1;i++){
int x = i-1;
long B = -b*x;
long C = dp[x] + b*x*(x+1)/2+a*x;
long lwhen = Long.MIN_VALUE;
while(qp > 0){
int lx = q[qp-1];
long LB = -b*lx;
long LC = dp[lx] + b*lx*(lx+1)/2+a*lx;
// B*x+C <= LB*x+LC
long when = (C-LC+(LB-B-1))/(LB-B);
if(qw[qp-1] >= when){
qp--;
}else{
lwhen = when;
break;
}
}
q[qp] = x;
qw[qp] = lwhen;
qp++;
int ind = Arrays.binarySearch(qw, 0, qp, i);
if(ind < 0)ind = -ind-2;
x = q[ind];
long val = dp[x] + b*(i-x)*(i-x-1)/2 - a*(i-x-1);
dp[i] = val + d[i-1];
}
out.println(dp[n+1]);
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
// @Override
// public void run() {
// long s = System.currentTimeMillis();
// solve();
// out.flush();
// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// }
// };
// t.start();
// t.join();
}
public static void main(String[] args) throws Exception { new N409().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private long[] nal(int n)
{
long[] a = new long[n];
for(int i = 0;i < n;i++)a[i] = nl();
return a;
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[][] nmi(int n, int m) {
int[][] map = new int[n][];
for(int i = 0;i < n;i++)map[i] = na(m);
return map;
}
private int ni() { return (int)nl(); }
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0