結果
| 問題 | No.2922 Rose Garden |
| ユーザー |
 hirohiso
|
| 提出日時 | 2024-10-12 15:34:39 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 10,654 bytes |
| コンパイル時間 | 4,355 ms |
| コンパイル使用メモリ | 104,448 KB |
| 実行使用メモリ | 763,072 KB |
| 最終ジャッジ日時 | 2024-10-12 15:35:10 |
| 合計ジャッジ時間 | 29,772 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | MLE | - |
| testcase_02 | MLE | - |
| testcase_03 | MLE | - |
| testcase_04 | MLE | - |
| testcase_05 | AC | 2,697 ms
363,936 KB |
| testcase_06 | TLE | - |
| testcase_07 | MLE | - |
| testcase_08 | AC | 2,260 ms
344,648 KB |
| testcase_09 | MLE | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.Format;
import java.util.*;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.IntPredicate;
import java.util.function.Predicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
@SuppressWarnings("unchecked")
public class Main {
public static void main(String[] args) {
solve(System.in, System.out);
}
private void solve(PrintWriter pw, FastScanner fs) {
var N = fs.ni();
var S = fs.ni();
var B = fs.nl();
var Hn = fs.nla(N);
var nowS = S;
var nowH = Hn[0];
var dp = new long[N][S + 1];
for (int i = 0; i < N; i++) {
for (int j = 0; j < S + 1; j++) {
dp[i][j] = -1;
}
}
dp[0][S] = Hn[0];
for (int i = 0; i < N - 1; i++) {
var check = false;
debug(i);
debugArray(dp[i]);
for (int j = 0; j < S + 1; j++) {
if (dp[i][j] >= 0) {
check = true;
}
}
if (!check) {
pw.println("No");
return;
}
//着地したケースも作る
dp[i][S] = Hn[i];
for (int j = S; j >= 0; j--) {
//高度が足りているなら隣へ移動する
if (dp[i][j] >= Hn[i + 1]) {
dp[i + 1][j] = Math.max(dp[i][j], dp[i + 1][j]);
}
//スタミナを減らして上昇する
if (j > 0) {
dp[i][j - 1] = Math.max(dp[i][j] + B, dp[i][j - 1]);
}
}
}
var check = false;
for (int j = 0; j < S + 1; j++) {
if (dp[N - 1][j] >= 0) {
check = true;
}
}
if (!check) {
pw.println("No");
return;
}
pw.println("Yes");
}
//--------------
record TPair<S, T>(S a, T b) {
}
record TTri<S, T, U>(S a, T b, U c) {
}
record Pair(long a, long b) {
}
record IntPair(int a, int b) {
}
record Triple(long a, long b, long c) {
}
public static int[] concat(int[] a, int[] b) {
var ret = new int[a.length + b.length];
for (int i = 0; i < a.length; i++) {
ret[i] = a[i];
}
for (int i = 0; i < b.length; i++) {
ret[i + a.length] = b[i];
}
return ret;
}
public static long[] concat(long[] a, long[] b) {
var ret = new long[a.length + b.length];
for (int i = 0; i < a.length; i++) {
ret[i] = a[i];
}
for (int i = 0; i < b.length; i++) {
ret[i + a.length] = b[i];
}
return ret;
}
public static void solve(InputStream in, PrintStream out) {
PrintWriter pw = new PrintWriter(out);
FastScanner fs = new FastScanner(in);
try {
new Main().solve(pw, fs);
} finally {
pw.flush();
}
}
//-------------------------------------------------------------------
private static void debug(Object x) {
System.err.println(x);
}
private static void debugArray(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
debugArray(arr[i]);
}
}
private static void debugArray(long[][] arr) {
for (int i = 0; i < arr.length; i++) {
debugArray(arr[i]);
}
}
private static void debugArray(int[] arr) {
debug(Arrays.toString(arr));
}
private static void debugArray(long[] arr) {
debug(Arrays.toString(arr));
}
private static void debugArray(boolean[] arr) {
debug(Arrays.toString(arr));
}
private static void debugArray(boolean[][] arr) {
for (int i = 0; i < arr.length; i++) {
debugArray(arr[i]);
}
}
/**
* 各インデックスが配列の長さ以内に収まっているか境界チェックを行う
* <p>
* 多次元配列のチェックをいちいち書くのがしんどい時に。
* arrayBound(new int[]{1,2,3} , new int[]{3,4,3})
*
* @param target 配列に設定したいインデックス
* @param len 配列の長さ
* @return 配列の長さ内に収まってる時 true
*/
private static boolean inarr(int[] target, int[] len) {
var b = true;
if (target.length != len.length) {
throw new IllegalArgumentException();
}
for (int i = 0; i < target.length; i++) {
b &= (0 <= target[i] && target[i] < len[i]);
}
return b;
}
private static int[] arr(int... a) {
return Arrays.copyOf(a, a.length);
}
private static long[] arr(long... a) {
return Arrays.copyOf(a, a.length);
}
//半時計90度回転
private static int[][] rot(int[][] grid) {
var h = grid.length;
var w = grid[0].length;
var result = new int[w][h];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
result[w - 1 - j][i] = grid[i][j];
}
}
return result;
}
//http://fantom1x.blog130.fc2.com/blog-entry-194.html
/**
* <h1>指定した値以上の先頭のインデクスを返す</h1>
* <p>配列要素が０のときは、０が返る。</p>
*
* @param arr ： 探索対象配列(単調増加であること)
* @param value ： 探索する値
* @return<b>int</b> ： 探索した値以上で、先頭になるインデクス
*/
public static final int lowerBound(final long[] arr, final long value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] < value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
/**
* <h1>指定した値より大きい先頭のインデクスを返す</h1>
* <p>配列要素が０のときは、０が返る。</p>
*
* @param arr ： 探索対象配列(単調増加であること)
* @param value ： 探索する値
* @return<b>int</b> ： 探索した値より上で、先頭になるインデクス
*/
public static final int upperBound(final long[] arr, final long value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] <= value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
//----------------
//-------------------------------------------------------------------
}
class FastScanner {
InputStream in;
byte[] buffer = new byte[1 << 10];
int length = 0;
int ptr = 0;
private final Predicate<Byte> isPrintable;
public FastScanner(InputStream in) {
this.in = in;
this.isPrintable = b -> (33 <= b && b <= 126);
}
public FastScanner(InputStream in, Predicate<Byte> predicate) {
this.in = in;
this.isPrintable = predicate;
}
private boolean hasNextByte() {
if (ptr < length) {
return true;
}
try {
length = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
ptr = 0;
return length != 0;
}
private byte read() {
if (hasNextByte()) {
return buffer[ptr++];
}
return 0;
}
private void skip() {
while (hasNextByte() && !isPrintable(buffer[ptr])) {
ptr++;
}
}
private boolean hasNext() {
skip();
return hasNextByte();
}
private boolean isPrintable(byte b) {
return 33 <= b && b <= 126;
}
private String innerNext(Predicate<Byte> isReadable) {
if (!hasNext()) {
throw new NoSuchElementException();
}
StringBuilder sb = new StringBuilder();
byte b = read();
while (isReadable.test(b)) {
sb.appendCodePoint(b);
b = read();
}
return sb.toString();
}
public String n() {
return innerNext(b -> (33 <= b && b <= 126));
}
public int ni() {
return (int) nl();
}
public char[][] ncaa(int n, int m) {
var grid = new char[n][m];
for (int i = 0; i < n; i++) {
grid[i] = n().toCharArray();
}
return grid;
}
public int[] nia(int n) {
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[i] = ni();
}
return result;
}
public int[][] niaa(int h, int w) {
int[][] result = new int[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
result[i][j] = ni();
}
}
return result;
}
public long[][] nlaa(int h, int w) {
long[][] result = new long[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
result[i][j] = nl();
}
}
return result;
}
public String[] na(int n) {
String[] result = new String[n];
for (int i = 0; i < n; i++) {
result[i] = n();
}
return result;
}
public long[] nla(int n) {
long[] result = new long[n];
for (int i = 0; i < n; i++) {
result[i] = nl();
}
return result;
}
public long nl() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long result = 0;
boolean minus = false;
byte b;
b = read();
if (b == '-') {
minus = true;
b = read();
}
while (isPrintable(b)) {
if (b < '0' || b > '9') {
throw new NumberFormatException();
}
result *= 10;
result += (b - '0');
b = read();
}
return minus ? -result : result;
}
}