結果
問題 | No.2328 Build Walls |
ユーザー | CuriousFairy315 |
提出日時 | 2023-05-28 15:02:56 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 424 ms / 3,000 ms |
コード長 | 9,978 bytes |
コンパイル時間 | 3,903 ms |
コンパイル使用メモリ | 83,820 KB |
実行使用メモリ | 64,708 KB |
最終ジャッジ日時 | 2023-08-27 11:16:50 |
合計ジャッジ時間 | 12,241 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 56 ms
50,364 KB |
testcase_01 | AC | 54 ms
50,220 KB |
testcase_02 | AC | 56 ms
50,136 KB |
testcase_03 | AC | 55 ms
50,140 KB |
testcase_04 | AC | 56 ms
50,236 KB |
testcase_05 | AC | 55 ms
50,164 KB |
testcase_06 | AC | 55 ms
50,208 KB |
testcase_07 | AC | 57 ms
50,208 KB |
testcase_08 | AC | 56 ms
50,156 KB |
testcase_09 | AC | 55 ms
50,176 KB |
testcase_10 | AC | 56 ms
50,212 KB |
testcase_11 | AC | 54 ms
50,064 KB |
testcase_12 | AC | 55 ms
50,148 KB |
testcase_13 | AC | 153 ms
57,292 KB |
testcase_14 | AC | 268 ms
57,976 KB |
testcase_15 | AC | 241 ms
59,828 KB |
testcase_16 | AC | 116 ms
54,016 KB |
testcase_17 | AC | 230 ms
58,524 KB |
testcase_18 | AC | 66 ms
50,988 KB |
testcase_19 | AC | 86 ms
54,304 KB |
testcase_20 | AC | 108 ms
54,340 KB |
testcase_21 | AC | 138 ms
56,624 KB |
testcase_22 | AC | 293 ms
59,916 KB |
testcase_23 | AC | 424 ms
64,292 KB |
testcase_24 | AC | 334 ms
63,864 KB |
testcase_25 | AC | 369 ms
63,516 KB |
testcase_26 | AC | 341 ms
64,708 KB |
testcase_27 | AC | 326 ms
63,804 KB |
testcase_28 | AC | 137 ms
60,524 KB |
testcase_29 | AC | 347 ms
63,820 KB |
testcase_30 | AC | 180 ms
61,312 KB |
testcase_31 | AC | 161 ms
60,288 KB |
testcase_32 | AC | 323 ms
64,220 KB |
testcase_33 | AC | 342 ms
63,784 KB |
testcase_34 | AC | 191 ms
61,548 KB |
testcase_35 | AC | 361 ms
62,000 KB |
testcase_36 | AC | 54 ms
50,152 KB |
ソースコード
import java.util.PriorityQueue; public class Main { public static void main(String[] args) { new Main(); } public Main() { FastScanner fs = new FastScanner(); java.io.PrintWriter out = new java.io.PrintWriter(System.out); solve(fs, out); out.flush(); } public void solve(FastScanner fs, java.io.PrintWriter out) { int H = fs.nextInt() - 2, W = fs.nextInt(); int[] A = new int[(H + 2) * (W + 4)]; java.util.Arrays.fill(A, -1); for (int y = 1;y <= H;++ y) { A[y * (W + 4) + 1] = A[(y + 1) * (W + 4) - 2] = 0; for (int x = 2;x < W + 2;++ x) { A[y * (W + 4) + x] = fs.nextInt(); } } int[] around = {1, -W - 3, -W - 4, -W - 5, -1, W + 3, W + 4, W + 5}; long[] dist = new long[A.length]; final long INF = IntMath.pow(10L, 18); java.util.Arrays.fill(dist, INF); class Pair { int p; long cost; Pair(int p) { this.p = p; cost = dist[p]; } } PriorityQueue<Pair> dijkstra = new PriorityQueue<>((l, r) -> Long.compare(l.cost, r.cost)); dist[W + 5] = 0; dijkstra.add(new Pair(W + 5)); while(!dijkstra.isEmpty()) { Pair p = dijkstra.poll(); int now = p.p; if (dist[now] != p.cost) continue; for (int d : around) { int next = now + d; if (A[next] == -1) continue; long nextCost = A[next] + p.cost; if (dist[next] <= nextCost) continue; dist[next] = nextCost; dijkstra.add(new Pair(next)); } } // for (int y = 0;y < H + 2;++ y) { // for (int x = 0;x < W + 4;++ x) { // out.print(dist[y * (W + 4) + x] + " "); // } // out.println(); // } long ans = dist[2 * W + 6]; if (ans == INF) ans = -1; out.println(ans); } final int MOD = 998_244_353; int plus(int n, int m) { int sum = n + m; if (sum >= MOD) sum -= MOD; return sum; } int minus(int n, int m) { int sum = n - m; if (sum < 0) sum += MOD; return sum; } int times(int n, int m) { return (int) ((long) n * m % MOD); } int divide(int n, int m) { return times(n, IntMath.pow(m, MOD - 2, MOD)); } int[] fact, invf; void calc(int len) { len += 2; fact = new int[len]; invf = new int[len]; fact[0] = fact[1] = invf[0] = invf[1] = 1; for (int i = 2; i < fact.length; ++i) fact[i] = times(fact[i - 1], i); invf[len - 1] = divide(1, fact[len - 1]); for (int i = len - 1; i > 1; --i) invf[i - 1] = times(i, invf[i]); } int comb(int n, int m) { if (n < m) return 0; return times(fact[n], times(invf[n - m], invf[m])); } } class FastScanner { private final java.io.InputStream in = System.in; private final byte[] buffer = new byte[8192]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) return true; ptr = 0; try { buflen = in.read(buffer); } catch (java.io.IOException e) { e.printStackTrace(); } return buflen > 0; } private byte readByte() { return hasNextByte() ? buffer[ptr++] : -1; } private static boolean isPrintableChar(byte c) { return 32 < c || c < 0; } private static boolean isNumber(int c) { return '0' <= c && c <= '9'; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte(); } public String next() { if (!hasNext()) throw new java.util.NoSuchElementException(); StringBuilder sb = new StringBuilder(); byte b; while (isPrintableChar(b = readByte())) sb.appendCodePoint(b); return sb.toString(); } public final char nextChar() { if (!hasNext()) throw new java.util.NoSuchElementException(); return (char) readByte(); } public final long nextLong() { if (!hasNext()) throw new java.util.NoSuchElementException(); long n = 0; try { byte b = readByte(); if (b == '-') { while (isNumber(b = readByte())) n = n * 10 + '0' - b; return n; } else if (!isNumber(b)) throw new NumberFormatException(); do n = n * 10 + b - '0'; while (isNumber(b = readByte())); } catch (java.util.NoSuchElementException e) {} return n; } public final int nextInt() { if (!hasNext()) throw new java.util.NoSuchElementException(); int n = 0; try { byte b = readByte(); if (b == '-') { while (isNumber(b = readByte())) n = n * 10 + '0' - b; return n; } else if (!isNumber(b)) throw new NumberFormatException(); do n = n * 10 + b - '0'; while (isNumber(b = readByte())); } catch (java.util.NoSuchElementException e) {} return n; } public double nextDouble() { return Double.parseDouble(next()); } } class Arrays { public static void sort(final int[] array) { sort(array, 0, array.length); } public static void sort(final int[] array, int fromIndex, int toIndex) { if (toIndex - fromIndex <= 512) { java.util.Arrays.sort(array, fromIndex, toIndex); return; } sort(array, fromIndex, toIndex, 0, new int[array.length]); } private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) { if (to - from <= 512) { java.util.Arrays.sort(a, from, to); return; } final int BUCKET_SIZE = 256; final int INT_RECURSION = 4; final int MASK = 0xff; final int shift = l << 3; final int[] cnt = new int[BUCKET_SIZE + 1]; final int[] put = new int[BUCKET_SIZE]; for (int i = from; i < to; i++) ++cnt[(a[i] >>> shift & MASK) + 1]; for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i]; for (int i = from; i < to; i++) { int bi = a[i] >>> shift & MASK; bucket[cnt[bi] + put[bi]++] = a[i]; } for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) { int begin = cnt[i]; int len = cnt[i + 1] - begin; System.arraycopy(bucket, begin, a, idx, len); idx += len; } final int nxtL = l + 1; if (nxtL < INT_RECURSION) { sort(a, from, to, nxtL, bucket); if (l == 0) { int lft, rgt; lft = from - 1; rgt = to; while (rgt - lft > 1) { int mid = lft + rgt >> 1; if (a[mid] < 0) lft = mid; else rgt = mid; } reverse(a, from, rgt); reverse(a, rgt, to); } } } public static void sort(final long[] array) { sort(array, 0, array.length); } public static void sort(final long[] array, int fromIndex, int toIndex) { if (toIndex - fromIndex <= 512) { java.util.Arrays.sort(array, fromIndex, toIndex); return; } sort(array, fromIndex, toIndex, 0, new long[array.length]); } private static final void sort(long[] a, final int from, final int to, final int l, final long[] bucket) { final int BUCKET_SIZE = 256; final int LONG_RECURSION = 8; final int MASK = 0xff; final int shift = l << 3; final int[] cnt = new int[BUCKET_SIZE + 1]; final int[] put = new int[BUCKET_SIZE]; for (int i = from; i < to; i++) ++cnt[(int) ((a[i] >>> shift & MASK) + 1)]; for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i]; for (int i = from; i < to; i++) { int bi = (int) (a[i] >>> shift & MASK); bucket[cnt[bi] + put[bi]++] = a[i]; } for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) { int begin = cnt[i]; int len = cnt[i + 1] - begin; System.arraycopy(bucket, begin, a, idx, len); idx += len; } final int nxtL = l + 1; if (nxtL < LONG_RECURSION) { sort(a, from, to, nxtL, bucket); if (l == 0) { int lft, rgt; lft = from - 1; rgt = to; while (rgt - lft > 1) { int mid = lft + rgt >> 1; if (a[mid] < 0) lft = mid; else rgt = mid; } reverse(a, from, rgt); reverse(a, rgt, to); } } } public static void reverse(int[] array) { reverse(array, 0, array.length); } public static void reverse(int[] array, int fromIndex, int toIndex) { for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) { int swap = array[fromIndex]; array[fromIndex] = array[toIndex]; array[toIndex] = swap; } } public static void reverse(long[] array) { reverse(array, 0, array.length); } public static void reverse(long[] array, int fromIndex, int toIndex) { for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) { long swap = array[fromIndex]; array[fromIndex] = array[toIndex]; array[toIndex] = swap; } } public static void shuffle(int[] array) { java.util.Random rnd = new java.util.Random(); for (int i = 0; i < array.length; ++i) { int j = rnd.nextInt(array.length - i) + i; int swap = array[i]; array[i] = array[j]; array[j] = swap; } } public static void shuffle(long[] array) { java.util.Random rnd = new java.util.Random(); for (int i = 0; i < array.length; ++i) { int j = rnd.nextInt(array.length - i) + i; long swap = array[i]; array[i] = array[j]; array[j] = swap; } } } class IntMath { public static int gcd(int a, int b) { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; } public static int gcd(int... array) { int ret = array[0]; for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]); return ret; } public static long gcd(long a, long b) { while (a != 0) if ((b %= a) != 0) a %= b; else return a; return b; } public static long gcd(long... array) { long ret = array[0]; for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]); return ret; } public static long lcm(long a, long b) { return a / gcd(a, b) * b; } public static int pow(int a, int b) { int ans = 1; for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static long pow(long a, long b) { long ans = 1; for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static int pow(int a, long b, int mod) { if (b < 0) b = b % (mod - 1) + mod - 1; long ans = 1; for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod) if ((b & 1) != 0) ans = ans * mul % mod; return (int) ans; } public static int pow(long a, long b, int mod) { return pow((int) (a % mod), b, mod); } public static int floorsqrt(long n) { return (int) Math.sqrt(n + 0.1); } public static int ceilsqrt(long n) { return n <= 1 ? (int) n : (int) Math.sqrt(n - 0.1) + 1; } }