#757988 (Java21) No.1460 Max of Min

提出ソース

結果

問題	No.1460 Max of Min
ユーザー	cyclerecycle9
提出日時	2022-05-04 03:19:07
言語	Java21 (openjdk 21)
結果	AC
実行時間	480 ms / 2,000 ms
コード長	4,785 bytes
コンパイル時間	2,546 ms
コンパイル使用メモリ	85,736 KB
実行使用メモリ	56,764 KB
最終ジャッジ日時	2024-07-03 03:42:31
合計ジャッジ時間	22,917 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	47 ms 36,544 KB
testcase_01	AC	48 ms 36,708 KB
testcase_02	AC	47 ms 36,684 KB
testcase_03	AC	409 ms 56,764 KB
testcase_04	AC	416 ms 56,764 KB
testcase_05	AC	48 ms 36,708 KB
testcase_06	AC	444 ms 56,352 KB
testcase_07	AC	434 ms 56,620 KB
testcase_08	AC	50 ms 36,924 KB
testcase_09	AC	46 ms 36,976 KB
testcase_10	AC	480 ms 56,648 KB
testcase_11	AC	412 ms 56,596 KB
testcase_12	AC	227 ms 43,316 KB
testcase_13	AC	274 ms 56,504 KB
testcase_14	AC	219 ms 48,196 KB
testcase_15	AC	139 ms 39,928 KB
testcase_16	AC	267 ms 56,356 KB
testcase_17	AC	231 ms 52,520 KB
testcase_18	AC	95 ms 38,480 KB
testcase_19	AC	233 ms 48,200 KB
testcase_20	AC	90 ms 38,864 KB
testcase_21	AC	132 ms 39,564 KB
testcase_22	AC	239 ms 48,276 KB
testcase_23	AC	87 ms 38,560 KB
testcase_24	AC	166 ms 46,356 KB
testcase_25	AC	85 ms 38,232 KB
testcase_26	AC	260 ms 56,728 KB
testcase_27	AC	132 ms 40,248 KB
testcase_28	AC	118 ms 38,744 KB
testcase_29	AC	219 ms 48,376 KB
testcase_30	AC	247 ms 56,332 KB
testcase_31	AC	217 ms 48,152 KB
testcase_32	AC	164 ms 51,364 KB
testcase_33	AC	68 ms 40,800 KB
testcase_34	AC	215 ms 48,036 KB
testcase_35	AC	99 ms 39,908 KB
testcase_36	AC	51 ms 37,360 KB
testcase_37	AC	120 ms 46,292 KB
testcase_38	AC	99 ms 49,904 KB
testcase_39	AC	202 ms 48,240 KB
testcase_40	AC	124 ms 40,664 KB
testcase_41	AC	115 ms 40,920 KB
testcase_42	AC	96 ms 39,068 KB
testcase_43	AC	239 ms 47,912 KB
testcase_44	AC	225 ms 52,656 KB
testcase_45	AC	92 ms 38,560 KB
testcase_46	AC	168 ms 43,324 KB
testcase_47	AC	223 ms 48,056 KB
testcase_48	AC	223 ms 52,432 KB
testcase_49	AC	137 ms 46,180 KB
testcase_50	AC	89 ms 38,848 KB
testcase_51	AC	204 ms 48,404 KB
testcase_52	AC	122 ms 39,708 KB
testcase_53	AC	140 ms 46,372 KB
testcase_54	AC	140 ms 50,284 KB
testcase_55	AC	158 ms 50,368 KB
testcase_56	AC	117 ms 54,580 KB
testcase_57	AC	236 ms 56,584 KB
testcase_58	AC	363 ms 52,448 KB
testcase_59	AC	147 ms 50,456 KB
testcase_60	AC	143 ms 50,108 KB
testcase_61	AC	142 ms 50,932 KB
testcase_62	AC	163 ms 51,068 KB
testcase_63	AC	75 ms 49,644 KB
testcase_64	AC	72 ms 49,564 KB
testcase_65	AC	248 ms 56,364 KB
testcase_66	AC	162 ms 50,820 KB
testcase_67	AC	77 ms 49,812 KB
testcase_68	AC	235 ms 56,608 KB
testcase_69	AC	227 ms 56,428 KB
testcase_70	AC	213 ms 56,268 KB
testcase_71	AC	234 ms 56,484 KB
testcase_72	AC	122 ms 50,384 KB
testcase_73	AC	116 ms 50,184 KB
testcase_74	AC	124 ms 54,768 KB
testcase_75	AC	112 ms 54,436 KB
testcase_76	AC	120 ms 54,572 KB
testcase_77	AC	123 ms 54,368 KB
testcase_78	AC	91 ms 50,124 KB
testcase_79	AC	130 ms 54,412 KB
testcase_80	AC	107 ms 50,308 KB
testcase_81	AC	90 ms 49,988 KB
testcase_82	AC	108 ms 54,264 KB
testcase_83	AC	102 ms 49,988 KB
testcase_84	AC	433 ms 52,540 KB
testcase_85	AC	412 ms 56,664 KB
testcase_86	AC	401 ms 52,556 KB
testcase_87	AC	402 ms 52,568 KB
testcase_88	AC	412 ms 56,564 KB
testcase_89	AC	422 ms 56,660 KB
testcase_90	AC	406 ms 56,592 KB
testcase_91	AC	419 ms 52,480 KB
testcase_92	AC	409 ms 56,360 KB
testcase_93	AC	402 ms 56,344 KB

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

ソースコード

raw source code

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;
		}
	}
}

yukicoder

結果

テストケース

ソースコード