結果
| 問題 | No.1460 Max of Min |
| ユーザー |
 cyclerecycle9
|
| 提出日時 | 2022-05-04 02:01:30 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,680 bytes |
| コンパイル時間 | 2,603 ms |
| コンパイル使用メモリ | 91,296 KB |
| 実行使用メモリ | 121,656 KB |
| 最終ジャッジ日時 | 2024-07-03 01:41:17 |
| 合計ジャッジ時間 | 6,781 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 61 ms
37,472 KB |
| testcase_01 | AC | 61 ms
37,292 KB |
| testcase_02 | AC | 60 ms
37,376 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| 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 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
ソースコード
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[] a = new Long[k];
Long[] init = new Long[k];
for (int i = 0; i < init.length; i++) {
init[i] = sc.nextLong();
}
for (int i = 0; i < init.length; i++) {
a[i] = sc.nextLong();
}
kitamasa<Long> KITA = new kitamasa<Long>(k, a, (x,y)->Math.max(x, y), (x,y)->Math.min(x, y), Long.MIN_VALUE);
System.out.println(KITA.calc(init, n));
}
//きたまさ法, k項間線形漸化式の第n項をO(k^2logn)で求める
//0index-dで0~k-1項を初項として計算する
//コンストラクタに漸化式の係数を与えて初期化。calcで初項を与えて計算する。
//注) aもinitも小さい順に入れていく、a_k = c_k-1*a_k-1 + .... + c_0*a_0 なら添え字の通りにいれる
//op1には+部分のop2には*部分の演算をいれる。op1は交換法則と結合法則を、op2は結合法則を満たす、op1とop2は分配法則を満たす。
static class kitamasa<T>{
int k;
T[] a;
java.util.function.BinaryOperator<T> op1;
java.util.function.BinaryOperator<T> op2;
T E;
T[][] x;
@SuppressWarnings("unchecked")
public kitamasa(int k, T[] a, java.util.function.BinaryOperator<T> op1, java.util.function.BinaryOperator<T> op2, T e) {
this.k = k;
this.a = (T[]) new Object[k];
for (int i = 0; i < a.length; i++) {
this.a[i] = a[i];
}
this.op1 = op1;
this.op2 = op2;
this.E = e;
this.x = (T[][]) new Object[k][k];
for (int i = 0; i < x.length; i++) {
Arrays.fill(x[i], E);
}
}
@SuppressWarnings("unchecked")
T[] dfs(long n){
if(n == k) return a;
T[] res = (T[]) new Object[k];
Arrays.fill(res, E);
if((n & 1) == 1 || n < k * 2){
T[] 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++){
T ret = op2.apply(x[0][i] , x[i][j]);
res[j] = op1.apply(res[j], ret);
}
}
}
return res;
}
void oneplus(T[] res, T[] x) {
for(int i = 0; i < k; i++) res[i] = op2.apply(a[i] , x[k - 1]);
for(int i = 0; i + 1 < k; i++) res[i + 1] = op1.apply(res[i + 1] , x[i]);
}
T calc(T[] init, long n) {
if(n<k) return init[(int)n];
T[] x = dfs(n);//a_nの係数
T res = E;
for (int i = 0; i < k; i++) {
T ret = op2.apply(init[i] , x[i]);
res = op1.apply(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;
}
}
}