結果
問題 | No.1460 Max of Min |
ユーザー | cyclerecycle9 |
提出日時 | 2022-05-04 02:57:51 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 801 ms / 2,000 ms |
コード長 | 5,104 bytes |
コンパイル時間 | 2,399 ms |
コンパイル使用メモリ | 75,908 KB |
実行使用メモリ | 473,060 KB |
最終ジャッジ日時 | 2023-09-16 01:55:38 |
合計ジャッジ時間 | 31,545 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
49,304 KB |
testcase_01 | AC | 42 ms
48,852 KB |
testcase_02 | AC | 42 ms
48,940 KB |
testcase_03 | AC | 785 ms
472,116 KB |
testcase_04 | AC | 801 ms
472,108 KB |
testcase_05 | AC | 42 ms
48,948 KB |
testcase_06 | AC | 781 ms
471,540 KB |
testcase_07 | AC | 778 ms
471,960 KB |
testcase_08 | AC | 43 ms
49,240 KB |
testcase_09 | AC | 42 ms
46,908 KB |
testcase_10 | AC | 776 ms
472,632 KB |
testcase_11 | AC | 776 ms
473,060 KB |
testcase_12 | AC | 220 ms
87,040 KB |
testcase_13 | AC | 421 ms
236,208 KB |
testcase_14 | AC | 265 ms
115,192 KB |
testcase_15 | AC | 133 ms
76,412 KB |
testcase_16 | AC | 356 ms
193,744 KB |
testcase_17 | AC | 250 ms
116,048 KB |
testcase_18 | AC | 85 ms
52,936 KB |
testcase_19 | AC | 301 ms
132,732 KB |
testcase_20 | AC | 86 ms
54,020 KB |
testcase_21 | AC | 125 ms
60,488 KB |
testcase_22 | AC | 310 ms
132,924 KB |
testcase_23 | AC | 87 ms
51,272 KB |
testcase_24 | AC | 233 ms
132,760 KB |
testcase_25 | AC | 72 ms
52,100 KB |
testcase_26 | AC | 417 ms
237,132 KB |
testcase_27 | AC | 151 ms
76,252 KB |
testcase_28 | AC | 111 ms
60,676 KB |
testcase_29 | AC | 295 ms
132,792 KB |
testcase_30 | AC | 329 ms
194,208 KB |
testcase_31 | AC | 285 ms
132,516 KB |
testcase_32 | AC | 184 ms
78,748 KB |
testcase_33 | AC | 60 ms
50,460 KB |
testcase_34 | AC | 192 ms
63,396 KB |
testcase_35 | AC | 98 ms
54,436 KB |
testcase_36 | AC | 45 ms
49,172 KB |
testcase_37 | AC | 128 ms
60,724 KB |
testcase_38 | AC | 87 ms
53,188 KB |
testcase_39 | AC | 176 ms
62,728 KB |
testcase_40 | AC | 122 ms
56,844 KB |
testcase_41 | AC | 112 ms
56,648 KB |
testcase_42 | AC | 87 ms
53,704 KB |
testcase_43 | AC | 236 ms
86,120 KB |
testcase_44 | AC | 247 ms
116,008 KB |
testcase_45 | AC | 84 ms
51,680 KB |
testcase_46 | AC | 181 ms
78,212 KB |
testcase_47 | AC | 224 ms
77,900 KB |
testcase_48 | AC | 261 ms
133,588 KB |
testcase_49 | AC | 175 ms
99,608 KB |
testcase_50 | AC | 87 ms
54,356 KB |
testcase_51 | AC | 223 ms
86,832 KB |
testcase_52 | AC | 128 ms
59,152 KB |
testcase_53 | AC | 131 ms
56,448 KB |
testcase_54 | AC | 108 ms
60,628 KB |
testcase_55 | AC | 219 ms
130,912 KB |
testcase_56 | AC | 103 ms
54,256 KB |
testcase_57 | AC | 251 ms
117,024 KB |
testcase_58 | AC | 784 ms
471,124 KB |
testcase_59 | AC | 166 ms
88,740 KB |
testcase_60 | AC | 180 ms
113,928 KB |
testcase_61 | AC | 132 ms
61,260 KB |
testcase_62 | AC | 149 ms
61,200 KB |
testcase_63 | AC | 49 ms
49,340 KB |
testcase_64 | AC | 50 ms
49,380 KB |
testcase_65 | AC | 301 ms
133,368 KB |
testcase_66 | AC | 156 ms
61,828 KB |
testcase_67 | AC | 53 ms
49,028 KB |
testcase_68 | AC | 252 ms
116,368 KB |
testcase_69 | AC | 245 ms
86,848 KB |
testcase_70 | AC | 227 ms
77,764 KB |
testcase_71 | AC | 293 ms
134,140 KB |
testcase_72 | AC | 108 ms
59,900 KB |
testcase_73 | AC | 105 ms
59,716 KB |
testcase_74 | AC | 121 ms
60,680 KB |
testcase_75 | AC | 109 ms
56,244 KB |
testcase_76 | AC | 97 ms
56,172 KB |
testcase_77 | AC | 93 ms
55,848 KB |
testcase_78 | AC | 71 ms
50,800 KB |
testcase_79 | AC | 95 ms
56,752 KB |
testcase_80 | AC | 89 ms
53,908 KB |
testcase_81 | AC | 71 ms
51,056 KB |
testcase_82 | AC | 93 ms
56,740 KB |
testcase_83 | AC | 81 ms
52,972 KB |
testcase_84 | AC | 772 ms
469,908 KB |
testcase_85 | AC | 761 ms
470,932 KB |
testcase_86 | AC | 745 ms
470,656 KB |
testcase_87 | AC | 759 ms
467,752 KB |
testcase_88 | AC | 756 ms
469,580 KB |
testcase_89 | AC | 768 ms
469,516 KB |
testcase_90 | AC | 760 ms
469,976 KB |
testcase_91 | AC | 760 ms
470,092 KB |
testcase_92 | AC | 765 ms
471,220 KB |
testcase_93 | AC | 751 ms
471,084 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); System.out.println(KITA.calc(init, n)); } //きたまさ法, k項間線形漸化式の第n項をO(k^2logn)で求める //注) aもinitも小さい順に入れていく、a_k = c_k-1*a_k-1 + .... + c_0*a_0 なら添え字の通りにいれる //0index-dで0~k-1項を初項として計算する //コンストラクタに漸化式の係数を与えて初期化。calcで初項を与えて計算する。 static class kitamasa{ int k; long[] a; public kitamasa(int k, long[] a) { this.k = k; this.a = new long[k]; for (int i = 0; i < a.length; i++) { this.a[i] = a[i]; } } long[] dfs(long n){ if(n == k) return a; long[] res = new long[k]; Arrays.fill(res, Long.MIN_VALUE); if((n & 1) == 1 || n < k * 2){ long[] x = dfs(n - 1); oneplus(res, x); } else{ long[][] x = new long[k][k]; for (int i = 0; i < x.length; i++) { Arrays.fill(x[i], Long.MIN_VALUE); } 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++){ res[j] = Math.max(res[j], Math.min(x[0][i] , x[i][j])); } } } return res; } void oneplus(long[] res, long[] x) { for(int i = 0; i < k; i++) res[i] = Math.min(a[i] , x[k - 1]); for(int i = 0; i + 1 < k; i++) res[i + 1] = Math.max(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 = Long.MIN_VALUE; for (int i = 0; i < k; i++) { res = Math.max(res, Math.min(init[i] , x[i])); } 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; } } }