結果

問題 No.2922 Rose Garden
ユーザー hirohisohirohiso
提出日時 2024-10-12 15:38:32
言語 Java21
(openjdk 21)
結果
AC  
実行時間 789 ms / 3,000 ms
コード長 10,668 bytes
コンパイル時間 3,508 ms
コンパイル使用メモリ 98,328 KB
実行使用メモリ 56,160 KB
最終ジャッジ日時 2024-10-12 15:38:59
合計ジャッジ時間 21,117 ms
ジャッジサーバーID
（参考情報） 		judge / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 252 ms
55,596 KB
testcase_01 AC 215 ms
55,680 KB
testcase_02 AC 493 ms
55,668 KB
testcase_03 AC 501 ms
55,580 KB
testcase_04 AC 510 ms
55,568 KB
testcase_05 AC 258 ms
55,292 KB
testcase_06 AC 272 ms
55,620 KB
testcase_07 AC 564 ms
55,612 KB
testcase_08 AC 238 ms
55,880 KB
testcase_09 AC 286 ms
55,480 KB
testcase_10 AC 115 ms
54,556 KB
testcase_11 AC 256 ms
55,544 KB
testcase_12 AC 299 ms
55,420 KB
testcase_13 AC 413 ms
55,244 KB
testcase_14 AC 178 ms
55,716 KB
testcase_15 AC 789 ms
55,720 KB
testcase_16 AC 551 ms
55,748 KB
testcase_17 AC 488 ms
55,636 KB
testcase_18 AC 199 ms
55,388 KB
testcase_19 AC 573 ms
56,160 KB
testcase_20 AC 671 ms
55,496 KB
testcase_21 AC 618 ms
55,624 KB
testcase_22 AC 164 ms
55,080 KB
testcase_23 AC 211 ms
55,256 KB
testcase_24 AC 213 ms
55,548 KB
testcase_25 AC 139 ms
55,012 KB
testcase_26 AC 684 ms
55,208 KB
testcase_27 AC 746 ms
55,240 KB
testcase_28 AC 224 ms
55,248 KB
testcase_29 AC 784 ms
55,504 KB
testcase_30 AC 146 ms
55,372 KB
testcase_31 AC 143 ms
55,284 KB
testcase_32 AC 150 ms
55,496 KB
testcase_33 AC 130 ms
54,840 KB
testcase_34 AC 143 ms
55,324 KB
testcase_35 AC 159 ms
55,508 KB
testcase_36 AC 206 ms
55,656 KB
testcase_37 AC 89 ms
51,560 KB
testcase_38 AC 121 ms
55,180 KB
testcase_39 AC 173 ms
55,352 KB
testcase_40 AC 568 ms
55,616 KB
testcase_41 AC 111 ms
54,424 KB
testcase_42 AC 287 ms
55,520 KB
testcase_43 AC 204 ms
55,436 KB
testcase_44 AC 261 ms
55,440 KB
testcase_45 AC 175 ms
55,584 KB
testcase_46 AC 139 ms
55,352 KB
testcase_47 AC 135 ms
55,020 KB
testcase_48 AC 94 ms
52,200 KB
testcase_49 AC 176 ms
55,420 KB
testcase_50 AC 57 ms
50,568 KB
testcase_51 AC 56 ms
50,284 KB
testcase_52 AC 57 ms
50,460 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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[S + 1];
        for (int j = 0; j < S + 1; j++) {
            dp[j] = -1;
        }

        dp[S] = Hn[0];
        for (int i = 0; i < N - 1; i++) {
            var check = false;
            var dpb = new long[S + 1];
            for (int j = 0; j < S + 1; j++) {
                dpb[j] = -1;
            }

            for (int j = 0; j < S + 1; j++) {
                if (dp[j] >= 0) {
                    check = true;
                }
            }
            if (!check) {
                pw.println("No");
                return;
            }
            //着地したケースも作る
            dp[S] = Hn[i];

            for (int j = S; j >= 0; j--) {
                //高度が足りているなら隣へ移動する
                if (dp[j] >= Hn[i + 1]) {
                    dpb[j] = Math.max(dp[j], dpb[j]);
                }
                //スタミナを減らして上昇する
                if (j > 0) {
                    dp[j - 1] = Math.max(dp[j] + B, dp[j - 1]);
                }
            }

            dp = dpb;
        }

        var check = false;
        for (int j = 0; j < S + 1; j++) {
            if (dp[j] >= 0) {
                check = true;
            }
        }
        if (!check) {
            pw.println("No");
            return;
        }
        debugArray(dp);
        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;
    }
}
0