#411499 (Java21) No.960 マンハッタン距離3

提出ソース

結果

問題	No.960 マンハッタン距離3
ユーザー	uwi
提出日時	2019-12-23 23:34:00
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	12,317 bytes
コンパイル時間	5,248 ms
コンパイル使用メモリ	90,696 KB
実行使用メモリ	88,612 KB
最終ジャッジ日時	2024-09-19 04:16:54
合計ジャッジ時間	56,304 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	56 ms 36,992 KB
testcase_01	AC	58 ms 36,940 KB
testcase_02	AC	57 ms 36,888 KB
testcase_03	AC	55 ms 37,052 KB
testcase_04	AC	58 ms 37,132 KB
testcase_05	AC	59 ms 36,968 KB
testcase_06	AC	57 ms 36,720 KB
testcase_07	AC	58 ms 36,724 KB
testcase_08	AC	58 ms 36,888 KB
testcase_09	AC	57 ms 36,960 KB
testcase_10	AC	56 ms 37,116 KB
testcase_11	AC	55 ms 36,896 KB
testcase_12	AC	55 ms 36,924 KB
testcase_13	AC	58 ms 36,948 KB
testcase_14	WA	-
testcase_15	AC	55 ms 36,928 KB
testcase_16	AC	57 ms 36,928 KB
testcase_17	AC	59 ms 36,928 KB
testcase_18	AC	60 ms 37,040 KB
testcase_19	AC	57 ms 36,896 KB
testcase_20	AC	59 ms 37,236 KB
testcase_21	AC	59 ms 37,188 KB
testcase_22	AC	57 ms 36,952 KB
testcase_23	AC	58 ms 36,928 KB
testcase_24	AC	58 ms 36,884 KB
testcase_25	AC	57 ms 36,864 KB
testcase_26	AC	56 ms 36,964 KB
testcase_27	AC	57 ms 36,896 KB
testcase_28	AC	58 ms 36,924 KB
testcase_29	AC	57 ms 37,012 KB
testcase_30	AC	59 ms 37,096 KB
testcase_31	AC	60 ms 36,712 KB
testcase_32	AC	57 ms 36,680 KB
testcase_33	AC	61 ms 37,080 KB
testcase_34	WA	-
testcase_35	AC	58 ms 36,844 KB
testcase_36	AC	60 ms 36,952 KB
testcase_37	AC	58 ms 36,932 KB
testcase_38	AC	59 ms 37,056 KB
testcase_39	AC	59 ms 36,920 KB
testcase_40	AC	59 ms 36,844 KB
testcase_41	AC	57 ms 37,120 KB
testcase_42	AC	58 ms 36,908 KB
testcase_43	AC	52 ms 36,724 KB
testcase_44	AC	51 ms 37,368 KB
testcase_45	AC	54 ms 36,840 KB
testcase_46	AC	52 ms 36,904 KB
testcase_47	WA	-
testcase_48	AC	53 ms 37,096 KB
testcase_49	AC	55 ms 37,140 KB
testcase_50	AC	53 ms 36,724 KB
testcase_51	AC	57 ms 37,240 KB
testcase_52	AC	53 ms 37,268 KB
testcase_53	AC	55 ms 37,004 KB
testcase_54	AC	54 ms 37,128 KB
testcase_55	AC	51 ms 37,108 KB
testcase_56	AC	59 ms 36,844 KB
testcase_57	AC	60 ms 36,932 KB
testcase_58	AC	59 ms 36,928 KB
testcase_59	AC	57 ms 36,844 KB
testcase_60	AC	60 ms 37,076 KB
testcase_61	AC	59 ms 37,264 KB
testcase_62	AC	59 ms 37,240 KB
testcase_63	AC	59 ms 37,108 KB
testcase_64	AC	58 ms 37,068 KB
testcase_65	AC	59 ms 37,000 KB
testcase_66	AC	58 ms 36,704 KB
testcase_67	AC	56 ms 36,916 KB
testcase_68	AC	59 ms 37,108 KB
testcase_69	AC	58 ms 36,960 KB
testcase_70	AC	59 ms 36,924 KB
testcase_71	AC	62 ms 37,136 KB
testcase_72	AC	60 ms 36,968 KB
testcase_73	AC	59 ms 36,968 KB
testcase_74	AC	61 ms 37,184 KB
testcase_75	AC	59 ms 37,148 KB
testcase_76	AC	58 ms 37,060 KB
testcase_77	AC	57 ms 36,960 KB
testcase_78	AC	59 ms 37,240 KB
testcase_79	AC	60 ms 37,092 KB
testcase_80	AC	61 ms 36,580 KB
testcase_81	AC	60 ms 36,780 KB
testcase_82	AC	58 ms 37,004 KB
testcase_83	AC	58 ms 37,112 KB
testcase_84	AC	57 ms 37,000 KB
testcase_85	AC	58 ms 37,144 KB
testcase_86	AC	57 ms 36,920 KB
testcase_87	AC	59 ms 37,012 KB
testcase_88	AC	58 ms 36,896 KB
testcase_89	AC	58 ms 37,240 KB
testcase_90	AC	57 ms 37,040 KB
testcase_91	AC	57 ms 36,908 KB
testcase_92	AC	57 ms 37,032 KB
testcase_93	AC	58 ms 36,888 KB
testcase_94	AC	58 ms 36,964 KB
testcase_95	AC	58 ms 36,860 KB
testcase_96	AC	58 ms 36,896 KB
testcase_97	AC	60 ms 36,972 KB
testcase_98	AC	57 ms 37,140 KB
testcase_99	AC	57 ms 36,596 KB
testcase_100	AC	60 ms 36,940 KB
testcase_101	AC	59 ms 36,964 KB
testcase_102	AC	57 ms 37,140 KB
testcase_103	AC	58 ms 36,888 KB
testcase_104	AC	57 ms 36,724 KB
testcase_105	AC	57 ms 37,060 KB
testcase_106	AC	58 ms 36,896 KB
testcase_107	AC	60 ms 36,668 KB
testcase_108	WA	-
testcase_109	WA	-
testcase_110	AC	58 ms 37,140 KB
testcase_111	AC	57 ms 36,876 KB
testcase_112	AC	58 ms 37,004 KB
testcase_113	AC	58 ms 36,940 KB
testcase_114	AC	58 ms 37,060 KB
testcase_115	AC	57 ms 37,276 KB
testcase_116	AC	56 ms 37,012 KB
testcase_117	AC	56 ms 36,904 KB
testcase_118	AC	56 ms 36,872 KB
testcase_119	AC	57 ms 36,728 KB
testcase_120	AC	58 ms 37,112 KB
testcase_121	AC	57 ms 36,844 KB
testcase_122	AC	58 ms 37,028 KB
testcase_123	AC	59 ms 36,608 KB
testcase_124	AC	58 ms 37,100 KB
testcase_125	AC	58 ms 36,968 KB
testcase_126	AC	59 ms 36,564 KB
testcase_127	AC	59 ms 36,932 KB
testcase_128	AC	309 ms 55,472 KB
testcase_129	AC	600 ms 75,476 KB
testcase_130	AC	523 ms 61,828 KB
testcase_131	AC	809 ms 78,596 KB
testcase_132	AC	928 ms 79,048 KB
testcase_133	AC	80 ms 38,492 KB
testcase_134	AC	135 ms 40,544 KB
testcase_135	AC	324 ms 56,036 KB
testcase_136	AC	357 ms 54,764 KB
testcase_137	AC	225 ms 55,360 KB
testcase_138	AC	658 ms 67,724 KB
testcase_139	AC	628 ms 75,336 KB
testcase_140	AC	267 ms 49,388 KB
testcase_141	AC	793 ms 79,764 KB
testcase_142	AC	385 ms 58,932 KB
testcase_143	AC	237 ms 57,192 KB
testcase_144	AC	646 ms 76,652 KB
testcase_145	AC	134 ms 40,936 KB
testcase_146	AC	258 ms 50,400 KB
testcase_147	AC	500 ms 66,372 KB
testcase_148	AC	386 ms 59,128 KB
testcase_149	AC	593 ms 70,336 KB
testcase_150	AC	677 ms 77,352 KB
testcase_151	AC	122 ms 40,732 KB
testcase_152	AC	227 ms 52,028 KB
testcase_153	AC	310 ms 59,796 KB
testcase_154	WA	-
testcase_155	AC	649 ms 75,680 KB
testcase_156	AC	303 ms 56,120 KB
testcase_157	AC	666 ms 75,752 KB
testcase_158	AC	825 ms 78,300 KB
testcase_159	AC	220 ms 51,108 KB
testcase_160	AC	121 ms 40,760 KB
testcase_161	AC	925 ms 76,732 KB
testcase_162	AC	263 ms 48,048 KB
testcase_163	AC	228 ms 55,168 KB
testcase_164	AC	988 ms 79,284 KB
testcase_165	AC	676 ms 75,944 KB
testcase_166	AC	215 ms 50,528 KB
testcase_167	AC	481 ms 60,912 KB
testcase_168	AC	366 ms 56,888 KB
testcase_169	AC	401 ms 59,020 KB
testcase_170	AC	325 ms 56,900 KB
testcase_171	WA	-
testcase_172	AC	398 ms 59,268 KB
testcase_173	AC	153 ms 42,304 KB
testcase_174	AC	719 ms 77,416 KB
testcase_175	AC	990 ms 80,484 KB
testcase_176	AC	646 ms 74,112 KB
testcase_177	AC	170 ms 45,676 KB
testcase_178	AC	692 ms 74,768 KB
testcase_179	AC	715 ms 76,732 KB
testcase_180	AC	262 ms 47,952 KB
testcase_181	AC	120 ms 40,252 KB
testcase_182	AC	161 ms 43,220 KB
testcase_183	AC	189 ms 45,112 KB
testcase_184	AC	161 ms 43,312 KB
testcase_185	AC	223 ms 46,628 KB
testcase_186	AC	234 ms 47,812 KB
testcase_187	AC	202 ms 45,732 KB
testcase_188	AC	58 ms 36,924 KB
testcase_189	AC	57 ms 36,944 KB
testcase_190	AC	58 ms 37,132 KB
testcase_191	AC	59 ms 37,100 KB
testcase_192	AC	58 ms 36,732 KB
testcase_193	AC	59 ms 36,916 KB
testcase_194	AC	57 ms 36,964 KB
testcase_195	AC	57 ms 36,960 KB
testcase_196	AC	520 ms 67,148 KB
testcase_197	AC	249 ms 49,996 KB
testcase_198	AC	442 ms 59,936 KB
testcase_199	AC	590 ms 73,964 KB
testcase_200	AC	237 ms 47,388 KB
testcase_201	AC	171 ms 43,560 KB
testcase_202	AC	601 ms 75,868 KB
testcase_203	AC	368 ms 58,908 KB
testcase_204	AC	776 ms 79,712 KB
testcase_205	AC	398 ms 60,104 KB
testcase_206	AC	351 ms 77,000 KB
testcase_207	AC	216 ms 46,888 KB
testcase_208	AC	598 ms 74,540 KB
testcase_209	AC	267 ms 54,144 KB
testcase_210	AC	174 ms 46,336 KB
testcase_211	AC	411 ms 58,268 KB
testcase_212	AC	170 ms 47,812 KB
testcase_213	AC	246 ms 58,432 KB
testcase_214	AC	817 ms 79,452 KB
testcase_215	AC	568 ms 77,108 KB
testcase_216	WA	-
testcase_217	WA	-
testcase_218	AC	265 ms 48,592 KB
testcase_219	AC	245 ms 58,944 KB

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

ソースコード

raw source code

package adv2019;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class D23_2 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	int w, h;
	int[][] co;
	
	void solve()
	{
		w = ni();
		h = ni();
		int n = ni();
		co = new int[n][];
		for(int i = 0;i < n;i++){
			co[i] = new int[]{ni(), ni(), -1, -1};
			co[i][2] = co[i][0] + co[i][1];
			co[i][3] = co[i][0] - co[i][1];
		}
		Arrays.sort(co, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				return a[0] - b[0];
			}
		});
		
		int[][] es = new int[6*n][];
		int p = 0;
		for(int i = 1;i < n;i++){
			int d = Math.abs(co[i][0] - co[0][0]) + 
					Math.abs(co[i][1] - co[0][1]);
			if(d % 2 != 0){
				out.println(0);
				return;
			}
			
			//    c
			// ab/d
			// ----e
			// ih\f
			//    g
			
			if(co[0][0] == co[i][0]){
				if(co[0][1] < co[i][1]){
					// a
					es[p++] = new int[]{
							1, co[0][1] + d/2, co[0][1] + d/2 + 1, 1, 0, i
					};
					es[p++] = new int[]{
							w+1, co[0][1] + d/2, co[0][1] + d/2 + 1, -1, 0, i
					};
				}else{
					// i
					es[p++] = new int[]{
							1, co[0][1] - d/2, co[0][1] - d/2 + 1, 1, 0, i
					};
					es[p++] = new int[]{
							w+1, co[0][1] - d/2, co[0][1] - d/2 + 1, -1, 0, i
					};
				}
			}else{
				if(co[0][1] < co[i][1]){
					if(co[0][3] > co[i][3]){
						// b
						es[p++] = new int[]{
								1, co[0][1] + d/2, co[0][1] + d/2 + 1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0], co[0][1] + d/2, co[0][1] + d/2 + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[0][0], co[0][1] + d/2, -1, 1, 2, i
						};
						es[p++] = new int[]{
								co[i][0], co[i][1] - d/2, -1, -1, 2, i
						};
						es[p++] = new int[]{
								co[i][0], co[i][1] - d/2, co[i][1] - d/2 + 1, 1, 0, i
						};
						es[p++] = new int[]{
								w+1, co[i][1] - d/2, co[i][1] - d/2 + 1, -1, 0, i
						};
					}else if(co[0][3] == co[i][3]){
						// c
						es[p++] = new int[]{
								1, co[i][1], h + 1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+1, co[i][1], h + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+1, co[i][1]-1, -1, 1, 2, i
						};
						es[p++] = new int[]{
								co[i][0], co[0][1], -1, -1, 2, i
						};
						es[p++] = new int[]{
								co[i][0], 1, co[0][1]+1, 1, 0, i
						};
						es[p++] = new int[]{
								w+1, 1, co[0][1]+1, -1, 0, i
						};
					}else{
						// d
						es[p++] = new int[]{
								co[i][0]-d/2, co[i][1], h + 1, 1, 0, i
						};
						es[p++] = new int[]{
								co[i][0]-d/2+1, co[i][1], h + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[i][0]-d/2, co[i][1], -1, 1, 2, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2, co[0][1], -1, -1, 2, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2, 1, co[0][1]+1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2+1, 1, co[0][1]+1, -1, 0, i
						};
					}
				}else if(co[0][1] == co[i][1]){
					// e
					es[p++] = new int[]{
							co[0][0]+d/2, 1, h + 1, 1, 0, i
					};
					es[p++] = new int[]{
							co[0][0]+d/2+1, 1, h+1, -1, 0, i
					};
				}else if(co[0][1] > co[i][1]){
					if(co[0][2] > co[i][2]){
						// h
						es[p++] = new int[]{
								1, co[0][1] - d/2, co[0][1] - d/2 + 1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0], co[0][1] - d/2, co[0][1] - d/2 + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[0][0], co[0][1] - d/2, 1, 1, 1, i
						};
						es[p++] = new int[]{
								co[i][0], co[i][1] + d/2, 1, -1, 1, i
						};
						es[p++] = new int[]{
								co[i][0], co[i][1] + d/2, co[i][1] + d/2 + 1, 1, 0, i
						};
						es[p++] = new int[]{
								w+1, co[i][1] + d/2, co[i][1] + d/2 + 1, -1, 0, i
						};
					}else if(co[0][2] == co[i][2]){
						// g
						es[p++] = new int[]{
								1, 1, co[i][1]+1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+1, 1, co[i][1] + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+1, co[i][1]+1, 1, 1, 1, i
						};
						es[p++] = new int[]{
								co[i][0], co[0][1], 1, -1, 1, i
						};
						es[p++] = new int[]{
								co[i][0], co[0][1], h+1, 1, 0, i
						};
						es[p++] = new int[]{
								w+1, co[0][1], h+1, -1, 0, i
						};
					}else{
						// f
						es[p++] = new int[]{
								co[i][0]-d/2, 1, co[i][1]+1, 1, 0, i
						};
						es[p++] = new int[]{
								co[i][0]-d/2+1, 1, co[i][1]+1, -1, 0, i
						};
						es[p++] = new int[]{
								co[i][0]-d/2+1, co[i][1]+1, 1, 1, 1, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2, co[0][1], 1, -1, 1, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2, co[0][1], h+1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2+1, co[0][1], h+1, -1, 0, i
						};
					}
				}
			}
		}
		es = Arrays.copyOf(es, p);
//		for(int[] e : es){
//			tr(e);
//		}
		Arrays.sort(es, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				return a[0] - b[0];
			}
		});
		
		MinHeap sups = new MinHeap(n);
		MinHeap infs = new MinHeap(n);
		long S02 = 0, S12 = 0, S22 = 0;
		long S01 = 0, S11 = 0, S21 = 0;
		int ins = 0;
		
		int x = 1;
		long S = 0;
		for(int[] e : es){
			if(x < e[0]){
				if(ins == n-1){
					boolean ok = true;
					if(S01 > 0){
						if(S11 % S01 == 0 && (S11/S01)*(S11/S01)*S01 == S21){
						}else{
							ok = false;
						}
					}
					if(S02 > 0){
						if(S12 % S02 == 0 && (S12/S02)*(S12/S02)*S02 == S22){
						}else{
							ok = false;
						}
					}
					
					if(ok){
//						tr(S01, S02, sups.size());
						if(S01 > 0 && S02 > 0){
							long ce1 = S11/S01;
							long ly1 = x+ce1;// y-x
							long ry1 = e[0]+ce1-1;

							long ce2 = S12/S02;
							long ly2 = ce2-x;// y+x
							long ry2 = ce2-e[0]+1;
							
							if((ly2-ly1) % 2 == 0 && ly1 <= ly2 && ry1 >= ry2){
								if(sups.size() == 0){
									S++;
								}else{
									long yy = (ly1+ly2)/2;
									long sup = sups.min();
									long inf = -infs.min();
									if(inf <= yy && yy < sup){
										S++;
									}
								}
							}
							
						}else if(S01 == 0 && S02 > 0){
							if(sups.size() == 0){
								S += e[0]-x;
							}else{
								long ce = S12/S02;
								long ly = ce-x+1;// y+x
								long ry = ce-e[0]+1;
								long sup = sups.min();
								long inf = -infs.min();
								inf = Math.max(inf, ry);
								sup = Math.min(sup, ly);
								S += Math.max(sup-inf, 0);
							}
						}else if(S02 == 0 && S01 > 0){
							if(sups.size() == 0){
								S += e[0]-x;
							}else{
								long ce = S11/S01;
								long ly = x+ce;// y-x
								long ry = e[0]+ce;
								long sup = sups.min();
								long inf = -infs.min();
								inf = Math.max(inf, ly);
								sup = Math.min(sup, ry);
								S += Math.max(sup-inf, 0);
							}
						}else{
							int sup = sups.min();
							int inf = -infs.min();
							if(inf < sup){
								S += (long)(sup-inf) * (e[0] - x);
							}
						}
//						tr(x, e[0], ins, n, S);
					}
				}
			}
			
			ins += e[3];
			if(e[4] == 0){
				// rectangle
				if(e[3] == 1){
					sups.add(e[5], e[2]);
					infs.add(e[5], -e[1]);
				}else{
					sups.remove(e[5]);
					infs.remove(e[5]);
				}
			}else if(e[4] == 1){
				// /
				S01 += e[3];
				S11 += e[3] * (e[1] - e[0]);
				S21 += (long)e[3] * (e[1] - e[0]) * (e[1] - e[0]);
			}else{
				// \
				S02 += e[3];
				S12 += e[3] * (e[1] + e[0]);
				S22 += (long)e[3] * (e[1] + e[0]) * (e[1] + e[0]);
			}
			x = e[0];
		}
		out.println(S);
	}
	
	public static class MinHeap {
		public int[] a;
		public int[] map;
		public int[] imap;
		public int n;
		public int pos;
		public static int INF = Integer.MAX_VALUE;
		
		public MinHeap(int m)
		{
			n = m+2;
			a = new int[n];
			map = new int[n];
			imap = new int[n];
			Arrays.fill(a, INF);
			Arrays.fill(map, -1);
			Arrays.fill(imap, -1);
			pos = 1;
		}
		
		public int add(int ind, int x)
		{
			int ret = imap[ind];
			if(imap[ind] < 0){
				a[pos] = x; map[pos] = ind; imap[ind] = pos;
				pos++;
				up(pos-1);
			}
			return ret != -1 ? a[ret] : x;
		}
		
		public int update(int ind, int x)
		{
			int ret = imap[ind];
			if(imap[ind] < 0){
				a[pos] = x; map[pos] = ind; imap[ind] = pos;
				pos++;
				up(pos-1);
			}else{
				int o = a[ret];
				a[ret] = x;
				up(ret);
				down(ret);
//				if(a[ret] > o){
//					up(ret);
//				}else{
//					down(ret);
//				}
			}
			return x;
		}
		
		public int remove(int ind)
		{
			if(pos == 1)return INF;
			if(imap[ind] == -1)return INF;
			
			pos--;
			int rem = imap[ind];
			int ret = a[rem];
			map[rem] = map[pos];
			imap[map[pos]] = rem;
			imap[ind] = -1;
			a[rem] = a[pos];
			a[pos] = INF;
			map[pos] = -1;
			
			up(rem);
			down(rem);
			return ret;
		}
		
		public int min() { return a[1]; }
		public int argmin() { return map[1]; }
		public int size() {	return pos-1; }
		
		private void up(int cur)
		{
			for(int c = cur, p = c>>>1;p >= 1 && a[p] > a[c];c>>>=1, p>>>=1){
				int d = a[p]; a[p] = a[c]; a[c] = d;
				int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e;
				e = map[p]; map[p] = map[c]; map[c] = e;
			}
		}
		
		private void down(int cur)
		{
			for(int c = cur;2*c < pos;){
				int b = a[2*c] < a[2*c+1] ? 2*c : 2*c+1;
				if(a[b] < a[c]){
					int d = a[c]; a[c] = a[b]; a[b] = d;
					int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e;
					e = map[c]; map[c] = map[b]; map[b] = e;
					c = b;
				}else{
					break;
				}
			}
		}
	}

	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//			@Override
//			public void run() {
//				long s = System.currentTimeMillis();
//				solve();
//				out.flush();
//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//			}
//		};
//		t.start();
//		t.join();
	}
	
	public static void main(String[] args) throws Exception { new D23_2().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

yukicoder

結果

テストケース

ソースコード