#903190 (Java21) No.2423 Merge Stones

提出ソース

結果

問題	No.2423 Merge Stones
ユーザー	hiromi_ayase
提出日時	2023-08-12 15:42:33
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	8,061 bytes
コンパイル時間	3,098 ms
コンパイル使用メモリ	92,196 KB
実行使用メモリ	68,012 KB
最終ジャッジ日時	2024-04-30 10:04:03
合計ジャッジ時間	9,840 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	69 ms 58,084 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	AC	65 ms 51,148 KB
testcase_05	AC	82 ms 52,672 KB
testcase_06	AC	84 ms 52,696 KB
testcase_07	WA	-
testcase_08	AC	83 ms 52,660 KB
testcase_09	AC	69 ms 51,116 KB
testcase_10	AC	84 ms 52,552 KB
testcase_11	TLE	-
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	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-
testcase_57	--	-
testcase_58	--	-
testcase_59	--	-
testcase_60	--	-
testcase_61	--	-
testcase_62	--	-
testcase_63	--	-
testcase_64	--	-
testcase_65	--	-
testcase_66	--	-
testcase_67	--	-
testcase_68	--	-
testcase_69	--	-
testcase_70	--	-
testcase_71	--	-
testcase_72	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.util.*;
import java.io.*;

@SuppressWarnings("unused")
public class Main {

  private static class SegTree<S> {
    final int MAX;

    final int N;
    final java.util.function.BinaryOperator<S> op;
    final S E;

    final S[] data;

    @SuppressWarnings("unchecked")
    public SegTree(int n, java.util.function.BinaryOperator<S> op, S e) {
      this.MAX = n;
      int k = 1;
      while (k < n)
        k <<= 1;
      this.N = k;
      this.E = e;
      this.op = op;
      this.data = (S[]) new Object[N << 1];
      java.util.Arrays.fill(data, E);
    }

    public SegTree(S[] dat, java.util.function.BinaryOperator<S> op, S e) {
      this(dat.length, op, e);
      build(dat);
    }

    private void build(S[] dat) {
      int l = dat.length;
      System.arraycopy(dat, 0, data, N, l);
      for (int i = N - 1; i > 0; i--) {
        data[i] = op.apply(data[i << 1 | 0], data[i << 1 | 1]);
      }
    }

    public void set(int p, S x) {
      exclusiveRangeCheck(p);
      data[p += N] = x;
      p >>= 1;
      while (p > 0) {
        data[p] = op.apply(data[p << 1 | 0], data[p << 1 | 1]);
        p >>= 1;
      }
    }

    public S get(int p) {
      exclusiveRangeCheck(p);
      return data[p + N];
    }

    public S prod(int l, int r) {
      if (l > r) {
        throw new IllegalArgumentException(
            String.format("Invalid range: [%d, %d)", l, r));
      }
      inclusiveRangeCheck(l);
      inclusiveRangeCheck(r);
      S sumLeft = E;
      S sumRight = E;
      l += N;
      r += N;
      while (l < r) {
        if ((l & 1) == 1)
          sumLeft = op.apply(sumLeft, data[l++]);
        if ((r & 1) == 1)
          sumRight = op.apply(data[--r], sumRight);
        l >>= 1;
        r >>= 1;
      }
      return op.apply(sumLeft, sumRight);
    }

    public S allProd() {
      return data[1];
    }

    public int maxRight(int l, java.util.function.Predicate<S> f) {
      inclusiveRangeCheck(l);
      if (!f.test(E)) {
        throw new IllegalArgumentException("Identity element must satisfy the condition.");
      }
      if (l == MAX)
        return MAX;
      l += N;
      S sum = E;
      do {
        l >>= Integer.numberOfTrailingZeros(l);
        if (!f.test(op.apply(sum, data[l]))) {
          while (l < N) {
            l = l << 1;
            if (f.test(op.apply(sum, data[l]))) {
              sum = op.apply(sum, data[l]);
              l++;
            }
          }
          return l - N;
        }
        sum = op.apply(sum, data[l]);
        l++;
      } while ((l & -l) != l);
      return MAX;
    }

    public int minLeft(int r, java.util.function.Predicate<S> f) {
      inclusiveRangeCheck(r);
      if (!f.test(E)) {
        throw new IllegalArgumentException("Identity element must satisfy the condition.");
      }
      if (r == 0)
        return 0;
      r += N;
      S sum = E;
      do {
        r--;
        while (r > 1 && (r & 1) == 1)
          r >>= 1;
        if (!f.test(op.apply(data[r], sum))) {
          while (r < N) {
            r = r << 1 | 1;
            if (f.test(op.apply(data[r], sum))) {
              sum = op.apply(data[r], sum);
              r--;
            }
          }
          return r + 1 - N;
        }
        sum = op.apply(data[r], sum);
      } while ((r & -r) != r);
      return 0;
    }

    private void exclusiveRangeCheck(int p) {
      if (p < 0 || p >= MAX) {
        throw new IndexOutOfBoundsException(
            String.format("Index %d out of bounds for the range [%d, %d).", p, 0, MAX));
      }
    }

    private void inclusiveRangeCheck(int p) {
      if (p < 0 || p > MAX) {
        throw new IndexOutOfBoundsException(
            String.format("Index %d out of bounds for the range [%d, %d].", p, 0, MAX));
      }
    }

    // **************** DEBUG **************** //

    private int indent = 6;

    public void setIndent(int newIndent) {
      this.indent = newIndent;
    }

    @Override
    public String toString() {
      return toSimpleString();
    }

    public String toDetailedString() {
      return toDetailedString(1, 0);
    }

    private String toDetailedString(int k, int sp) {
      if (k >= N)
        return indent(sp) + data[k];
      String s = "";
      s += toDetailedString(k << 1 | 1, sp + indent);
      s += "\n";
      s += indent(sp) + data[k];
      s += "\n";
      s += toDetailedString(k << 1 | 0, sp + indent);
      return s;
    }

    private static String indent(int n) {
      StringBuilder sb = new StringBuilder();
      while (n-- > 0)
        sb.append(' ');
      return sb.toString();
    }

    public String toSimpleString() {
      StringBuilder sb = new StringBuilder();
      sb.append('[');
      for (int i = 0; i < N; i++) {
        sb.append(data[i + N]);
        if (i < N - 1)
          sb.append(',').append(' ');
      }
      sb.append(']');
      return sb.toString();
    }
  }

  private static void solve() {
    int n = ni() * 2;
    int k = ni();
    int[] a = new int[n];
    int[] c = new int[n];
    for (int i = 0; i < n / 2; i++) {
      a[i] = a[i + n / 2] = ni();
    }
    for (int i = 0; i < n / 2; i++) {
      c[i] = c[i + n / 2] = ni();
    }

    var stMin = new SegTree<Integer>(n, (o1, o2) -> Math.min(o1, o2), Integer.MAX_VALUE);
    var stMax = new SegTree<Integer>(n, (o1, o2) -> Math.max(o1, o2), Integer.MIN_VALUE);
    for (int i = 0; i < n; i++) {
      stMin.set(i, c[i]);
      stMax.set(i, c[i]);
    }

    long[][] dp = new long[n][n + 1];
    for (var v : dp) Arrays.fill(v, Long.MIN_VALUE / 10000);
    long ret = 0;
    for (int len = 1; len <= n / 2; len++) {
      for (int l = 0; l < n; l++) {
        if (l + len > n) continue; 
        if (len == 1) {
          dp[l][l + 1] = a[l];
        } else {
          for (int j = l + 1; j < l + len; j++) {
            int stMinLeft = stMin.prod(l, j);
            int stMinRight = stMin.prod(j, l + len);
            int stMaxLeft = stMax.prod(l, j);
            int stMaxRight = stMax.prod(j, l + len);

            if (stMaxLeft + k >= stMinRight && stMaxRight + k >= stMinLeft) {
              dp[l][l + len] = Math.max(dp[l][l + len], dp[l][j] + dp[j][l + len]);
            }
          }
        }
        ret = Math.max(ret, dp[l][l + len]);
      }
    }
    //System.out.println(Arrays.deepToString(dp));
    System.out.println(ret);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        solve();
        out.flush();
      }
    }, "", 64000000).start();
  }

  private static PrintWriter out = new PrintWriter(System.out);
  private static StringTokenizer tokenizer = null;
  private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 32768);

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }
}

yukicoder

結果

テストケース

ソースコード