結果
問題 | No.1460 Max of Min |
ユーザー | cyclerecycle9 |
提出日時 | 2022-05-04 03:19:07 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 476 ms / 2,000 ms |
コード長 | 4,785 bytes |
コンパイル時間 | 2,890 ms |
コンパイル使用メモリ | 75,404 KB |
実行使用メモリ | 68,036 KB |
最終ジャッジ日時 | 2023-09-16 02:26:15 |
合計ジャッジ時間 | 25,345 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
49,468 KB |
testcase_01 | AC | 43 ms
49,744 KB |
testcase_02 | AC | 42 ms
49,488 KB |
testcase_03 | AC | 435 ms
65,648 KB |
testcase_04 | AC | 440 ms
67,632 KB |
testcase_05 | AC | 43 ms
49,448 KB |
testcase_06 | AC | 471 ms
67,376 KB |
testcase_07 | AC | 467 ms
68,036 KB |
testcase_08 | AC | 45 ms
49,436 KB |
testcase_09 | AC | 45 ms
49,444 KB |
testcase_10 | AC | 456 ms
66,804 KB |
testcase_11 | AC | 450 ms
66,796 KB |
testcase_12 | AC | 210 ms
56,548 KB |
testcase_13 | AC | 309 ms
67,296 KB |
testcase_14 | AC | 235 ms
58,008 KB |
testcase_15 | AC | 123 ms
52,444 KB |
testcase_16 | AC | 299 ms
67,076 KB |
testcase_17 | AC | 226 ms
62,764 KB |
testcase_18 | AC | 96 ms
51,540 KB |
testcase_19 | AC | 257 ms
58,224 KB |
testcase_20 | AC | 106 ms
52,452 KB |
testcase_21 | AC | 145 ms
52,608 KB |
testcase_22 | AC | 256 ms
58,320 KB |
testcase_23 | AC | 98 ms
51,556 KB |
testcase_24 | AC | 191 ms
57,000 KB |
testcase_25 | AC | 80 ms
51,660 KB |
testcase_26 | AC | 302 ms
67,056 KB |
testcase_27 | AC | 147 ms
52,484 KB |
testcase_28 | AC | 122 ms
50,864 KB |
testcase_29 | AC | 245 ms
58,152 KB |
testcase_30 | AC | 283 ms
67,320 KB |
testcase_31 | AC | 233 ms
58,120 KB |
testcase_32 | AC | 165 ms
61,232 KB |
testcase_33 | AC | 75 ms
51,980 KB |
testcase_34 | AC | 209 ms
59,012 KB |
testcase_35 | AC | 105 ms
52,332 KB |
testcase_36 | AC | 47 ms
49,412 KB |
testcase_37 | AC | 136 ms
58,916 KB |
testcase_38 | AC | 117 ms
61,216 KB |
testcase_39 | AC | 194 ms
58,668 KB |
testcase_40 | AC | 124 ms
54,396 KB |
testcase_41 | AC | 111 ms
54,768 KB |
testcase_42 | AC | 98 ms
52,384 KB |
testcase_43 | AC | 233 ms
58,300 KB |
testcase_44 | AC | 231 ms
62,772 KB |
testcase_45 | AC | 76 ms
51,408 KB |
testcase_46 | AC | 151 ms
55,384 KB |
testcase_47 | AC | 227 ms
58,440 KB |
testcase_48 | AC | 244 ms
62,768 KB |
testcase_49 | AC | 151 ms
56,576 KB |
testcase_50 | AC | 82 ms
52,352 KB |
testcase_51 | AC | 213 ms
58,404 KB |
testcase_52 | AC | 147 ms
52,444 KB |
testcase_53 | AC | 152 ms
56,872 KB |
testcase_54 | AC | 121 ms
60,564 KB |
testcase_55 | AC | 167 ms
60,628 KB |
testcase_56 | AC | 130 ms
64,664 KB |
testcase_57 | AC | 251 ms
67,388 KB |
testcase_58 | AC | 476 ms
63,444 KB |
testcase_59 | AC | 148 ms
61,004 KB |
testcase_60 | AC | 156 ms
60,388 KB |
testcase_61 | AC | 152 ms
60,908 KB |
testcase_62 | AC | 160 ms
60,756 KB |
testcase_63 | AC | 65 ms
59,884 KB |
testcase_64 | AC | 67 ms
59,840 KB |
testcase_65 | AC | 261 ms
66,936 KB |
testcase_66 | AC | 154 ms
60,688 KB |
testcase_67 | AC | 70 ms
59,888 KB |
testcase_68 | AC | 249 ms
66,900 KB |
testcase_69 | AC | 239 ms
66,856 KB |
testcase_70 | AC | 229 ms
66,816 KB |
testcase_71 | AC | 261 ms
67,752 KB |
testcase_72 | AC | 120 ms
60,616 KB |
testcase_73 | AC | 116 ms
60,928 KB |
testcase_74 | AC | 115 ms
64,908 KB |
testcase_75 | AC | 111 ms
64,928 KB |
testcase_76 | AC | 113 ms
64,988 KB |
testcase_77 | AC | 112 ms
65,196 KB |
testcase_78 | AC | 90 ms
60,188 KB |
testcase_79 | AC | 118 ms
65,600 KB |
testcase_80 | AC | 94 ms
60,576 KB |
testcase_81 | AC | 89 ms
58,484 KB |
testcase_82 | AC | 120 ms
65,132 KB |
testcase_83 | AC | 85 ms
59,860 KB |
testcase_84 | AC | 469 ms
62,728 KB |
testcase_85 | AC | 457 ms
66,768 KB |
testcase_86 | AC | 435 ms
63,056 KB |
testcase_87 | AC | 443 ms
62,736 KB |
testcase_88 | AC | 442 ms
66,940 KB |
testcase_89 | AC | 468 ms
66,932 KB |
testcase_90 | AC | 452 ms
66,652 KB |
testcase_91 | AC | 457 ms
62,472 KB |
testcase_92 | AC | 460 ms
66,780 KB |
testcase_93 | AC | 441 ms
66,804 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigDecimal; import java.math.RoundingMode; import java.util.*; public class Main { static final long MOD=1000000007; static final long MOD1=998244353; static int size = 0; static long MAX = 1000000000000000000l; public static void main(String[] args){ PrintWriter out = new PrintWriter(System.out); InputReader sc=new InputReader(System.in); int k = sc.nextInt(); long n = sc.nextLong(); long[] init = sc.nextLongArray(k); long[] a = sc.nextLongArray(k); kitamasa KITA = new kitamasa(k, a, Long.MIN_VALUE); System.out.println(KITA.calc(init, n)); } static class kitamasa{ int k; long[] a; long E; long[][] x; public kitamasa(int k, long[] a, long e) { this.k = k; this.a = new long[k]; for (int i = 0; i < a.length; i++) { this.a[i] = a[i]; } this.E = e; this.x = new long[k][k]; for (int i = 0; i < x.length; i++) { Arrays.fill(x[i], E); } } long op1(long t1, long t2) { return Math.max(t1, t2); } long op2(long t1, long t2) { return Math.min(t1, t2); } long[] dfs(long n){ if(n == k) return a; long[] res = new long[k]; Arrays.fill(res, E); if((n & 1) == 1 || n < k * 2){ long[] x = dfs(n - 1); oneplus(res, x); } else{ for (int i = 0; i < x.length; i++) { Arrays.fill(x[i], E); } x[0] = dfs(n >> 1); for(int i = 0; i + 1 < k; i++){ oneplus(x[i+1], x[i]); } for(int i = 0; i < k; i++){ for(int j = 0; j < k; j++){ long ret = op2(x[0][i] , x[i][j]); res[j] = op1(res[j], ret); } } } return res; } void oneplus(long[] res, long[] x) { for(int i = 0; i < k; i++) res[i] = op2(a[i] , x[k - 1]); for(int i = 0; i + 1 < k; i++) res[i + 1] = op1(res[i + 1] , x[i]); } long calc(long[] init, long n) { if(n<k) return init[(int)n]; long[] x = dfs(n);//a_nの係数 long res = E; for (int i = 0; i < k; i++) { long ret = op2(init[i] , x[i]); res = op1(res, ret); } return res; } } static class InputReader { private InputStream in; private byte[] buffer = new byte[1024]; private int curbuf; private int lenbuf; public InputReader(InputStream in) { this.in = in; this.curbuf = this.lenbuf = 0; } public boolean hasNextByte() { if (curbuf >= lenbuf) { curbuf = 0; try { lenbuf = in.read(buffer); } catch (IOException e) { throw new InputMismatchException(); } if (lenbuf <= 0) return false; } return true; } private int readByte() { if (hasNextByte()) return buffer[curbuf++]; else return -1; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private void skip() { while (hasNextByte() && isSpaceChar(buffer[curbuf])) curbuf++; } public boolean hasNext() { skip(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public int nextInt() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public double[] nextDoubleArray(int n) { double[] a = new double[n]; for (int i = 0; i < n; i++) a[i] = nextDouble(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } public char[][] nextCharMap(int n, int m) { char[][] map = new char[n][m]; for (int i = 0; i < n; i++) map[i] = next().toCharArray(); return map; } } }