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

提出ソース

結果

問題	No.960 マンハッタン距離3
ユーザー	uwi
提出日時	2019-12-23 23:34:00
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	12,317 bytes
コンパイル時間	5,531 ms
コンパイル使用メモリ	90,404 KB
実行使用メモリ	94,940 KB
最終ジャッジ日時	2023-10-19 08:00:20
合計ジャッジ時間	60,164 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	57 ms 52,524 KB
testcase_01	AC	56 ms 52,416 KB
testcase_02	AC	56 ms 52,552 KB
testcase_03	AC	56 ms 53,412 KB
testcase_04	AC	57 ms 52,544 KB
testcase_05	AC	56 ms 52,560 KB
testcase_06	AC	56 ms 53,492 KB
testcase_07	AC	55 ms 53,488 KB
testcase_08	AC	54 ms 53,420 KB
testcase_09	AC	55 ms 53,420 KB
testcase_10	AC	56 ms 53,484 KB
testcase_11	AC	54 ms 53,412 KB
testcase_12	AC	56 ms 53,420 KB
testcase_13	AC	55 ms 52,540 KB
testcase_14	WA	-
testcase_15	AC	55 ms 52,500 KB
testcase_16	AC	55 ms 53,424 KB
testcase_17	AC	58 ms 53,496 KB
testcase_18	AC	58 ms 52,568 KB
testcase_19	AC	56 ms 53,424 KB
testcase_20	AC	59 ms 53,516 KB
testcase_21	AC	91 ms 53,508 KB
testcase_22	AC	59 ms 52,400 KB
testcase_23	AC	56 ms 52,552 KB
testcase_24	AC	57 ms 53,496 KB
testcase_25	AC	58 ms 53,504 KB
testcase_26	AC	55 ms 53,412 KB
testcase_27	AC	55 ms 53,496 KB
testcase_28	AC	57 ms 53,504 KB
testcase_29	AC	56 ms 52,316 KB
testcase_30	AC	57 ms 53,496 KB
testcase_31	AC	58 ms 53,504 KB
testcase_32	AC	56 ms 53,444 KB
testcase_33	AC	58 ms 53,512 KB
testcase_34	WA	-
testcase_35	AC	56 ms 52,464 KB
testcase_36	AC	58 ms 53,504 KB
testcase_37	AC	56 ms 53,496 KB
testcase_38	AC	57 ms 53,524 KB
testcase_39	AC	56 ms 53,504 KB
testcase_40	AC	58 ms 53,516 KB
testcase_41	AC	56 ms 53,496 KB
testcase_42	AC	58 ms 53,508 KB
testcase_43	AC	56 ms 53,500 KB
testcase_44	AC	56 ms 53,428 KB
testcase_45	AC	55 ms 53,364 KB
testcase_46	AC	58 ms 53,504 KB
testcase_47	WA	-
testcase_48	AC	57 ms 53,500 KB
testcase_49	AC	57 ms 51,468 KB
testcase_50	AC	57 ms 52,560 KB
testcase_51	AC	56 ms 53,504 KB
testcase_52	AC	56 ms 53,500 KB
testcase_53	AC	57 ms 53,508 KB
testcase_54	AC	56 ms 53,420 KB
testcase_55	AC	60 ms 52,324 KB
testcase_56	AC	59 ms 53,496 KB
testcase_57	AC	58 ms 52,924 KB
testcase_58	AC	57 ms 52,920 KB
testcase_59	AC	56 ms 52,912 KB
testcase_60	AC	58 ms 53,504 KB
testcase_61	AC	57 ms 53,516 KB
testcase_62	AC	59 ms 53,504 KB
testcase_63	AC	58 ms 53,508 KB
testcase_64	AC	57 ms 53,508 KB
testcase_65	AC	56 ms 53,492 KB
testcase_66	AC	56 ms 53,496 KB
testcase_67	AC	57 ms 53,492 KB
testcase_68	AC	62 ms 53,436 KB
testcase_69	AC	58 ms 52,916 KB
testcase_70	AC	59 ms 53,504 KB
testcase_71	AC	57 ms 53,504 KB
testcase_72	AC	56 ms 53,372 KB
testcase_73	AC	57 ms 52,856 KB
testcase_74	AC	55 ms 52,100 KB
testcase_75	AC	56 ms 52,856 KB
testcase_76	AC	57 ms 52,300 KB
testcase_77	AC	56 ms 53,368 KB
testcase_78	AC	57 ms 52,852 KB
testcase_79	AC	57 ms 52,352 KB
testcase_80	AC	57 ms 53,488 KB
testcase_81	AC	56 ms 53,496 KB
testcase_82	AC	56 ms 53,416 KB
testcase_83	AC	56 ms 53,412 KB
testcase_84	AC	55 ms 52,296 KB
testcase_85	AC	55 ms 53,424 KB
testcase_86	AC	55 ms 51,380 KB
testcase_87	AC	59 ms 52,388 KB
testcase_88	AC	58 ms 53,492 KB
testcase_89	AC	58 ms 53,496 KB
testcase_90	AC	57 ms 53,500 KB
testcase_91	AC	57 ms 53,492 KB
testcase_92	AC	56 ms 53,424 KB
testcase_93	AC	56 ms 53,424 KB
testcase_94	AC	57 ms 53,504 KB
testcase_95	AC	56 ms 53,500 KB
testcase_96	AC	60 ms 53,504 KB
testcase_97	AC	58 ms 53,500 KB
testcase_98	AC	56 ms 52,468 KB
testcase_99	AC	58 ms 53,420 KB
testcase_100	AC	57 ms 52,924 KB
testcase_101	AC	56 ms 52,936 KB
testcase_102	AC	57 ms 52,920 KB
testcase_103	AC	57 ms 52,912 KB
testcase_104	AC	57 ms 53,412 KB
testcase_105	AC	58 ms 52,832 KB
testcase_106	AC	57 ms 53,496 KB
testcase_107	AC	59 ms 52,524 KB
testcase_108	WA	-
testcase_109	WA	-
testcase_110	AC	56 ms 53,416 KB
testcase_111	AC	56 ms 53,416 KB
testcase_112	AC	56 ms 53,496 KB
testcase_113	AC	56 ms 53,432 KB
testcase_114	AC	58 ms 52,412 KB
testcase_115	AC	55 ms 53,496 KB
testcase_116	AC	57 ms 52,916 KB
testcase_117	AC	57 ms 52,920 KB
testcase_118	AC	56 ms 52,836 KB
testcase_119	AC	55 ms 52,844 KB
testcase_120	AC	57 ms 52,916 KB
testcase_121	AC	55 ms 52,832 KB
testcase_122	AC	56 ms 52,832 KB
testcase_123	AC	57 ms 52,916 KB
testcase_124	AC	57 ms 52,404 KB
testcase_125	AC	56 ms 52,492 KB
testcase_126	AC	56 ms 52,832 KB
testcase_127	AC	57 ms 53,496 KB
testcase_128	AC	310 ms 68,792 KB
testcase_129	AC	596 ms 88,640 KB
testcase_130	AC	501 ms 75,840 KB
testcase_131	AC	751 ms 92,268 KB
testcase_132	AC	972 ms 92,372 KB
testcase_133	AC	79 ms 54,756 KB
testcase_134	AC	135 ms 55,948 KB
testcase_135	AC	327 ms 68,576 KB
testcase_136	AC	374 ms 68,772 KB
testcase_137	AC	224 ms 69,064 KB
testcase_138	AC	674 ms 81,808 KB
testcase_139	AC	620 ms 87,332 KB
testcase_140	AC	266 ms 62,956 KB
testcase_141	AC	795 ms 92,840 KB
testcase_142	AC	389 ms 71,936 KB
testcase_143	AC	243 ms 70,392 KB
testcase_144	AC	645 ms 89,812 KB
testcase_145	AC	135 ms 57,624 KB
testcase_146	AC	250 ms 65,124 KB
testcase_147	AC	586 ms 81,020 KB
testcase_148	AC	374 ms 72,180 KB
testcase_149	AC	598 ms 85,340 KB
testcase_150	AC	665 ms 90,420 KB
testcase_151	AC	121 ms 55,772 KB
testcase_152	AC	229 ms 67,232 KB
testcase_153	AC	312 ms 74,036 KB
testcase_154	WA	-
testcase_155	AC	645 ms 88,804 KB
testcase_156	AC	297 ms 70,024 KB
testcase_157	AC	685 ms 88,988 KB
testcase_158	AC	788 ms 91,704 KB
testcase_159	AC	219 ms 63,864 KB
testcase_160	AC	122 ms 55,888 KB
testcase_161	AC	907 ms 89,908 KB
testcase_162	AC	270 ms 62,356 KB
testcase_163	AC	231 ms 69,044 KB
testcase_164	AC	946 ms 92,576 KB
testcase_165	AC	664 ms 88,616 KB
testcase_166	AC	214 ms 63,804 KB
testcase_167	AC	467 ms 75,812 KB
testcase_168	AC	361 ms 68,724 KB
testcase_169	AC	411 ms 71,508 KB
testcase_170	AC	336 ms 68,576 KB
testcase_171	WA	-
testcase_172	AC	386 ms 71,972 KB
testcase_173	AC	155 ms 58,228 KB
testcase_174	AC	687 ms 89,988 KB
testcase_175	AC	996 ms 94,940 KB
testcase_176	AC	680 ms 87,180 KB
testcase_177	AC	176 ms 61,148 KB
testcase_178	AC	619 ms 86,124 KB
testcase_179	AC	703 ms 90,376 KB
testcase_180	AC	254 ms 62,328 KB
testcase_181	AC	123 ms 55,108 KB
testcase_182	AC	160 ms 58,732 KB
testcase_183	AC	192 ms 59,332 KB
testcase_184	AC	162 ms 58,752 KB
testcase_185	AC	223 ms 63,400 KB
testcase_186	AC	244 ms 62,356 KB
testcase_187	AC	204 ms 61,636 KB
testcase_188	AC	57 ms 53,432 KB
testcase_189	AC	59 ms 53,428 KB
testcase_190	AC	57 ms 52,580 KB
testcase_191	AC	57 ms 53,500 KB
testcase_192	AC	57 ms 53,488 KB
testcase_193	AC	58 ms 53,416 KB
testcase_194	AC	56 ms 52,448 KB
testcase_195	AC	56 ms 52,332 KB
testcase_196	AC	516 ms 80,584 KB
testcase_197	AC	242 ms 63,548 KB
testcase_198	AC	437 ms 72,668 KB
testcase_199	AC	579 ms 87,236 KB
testcase_200	AC	237 ms 62,840 KB
testcase_201	AC	166 ms 59,180 KB
testcase_202	AC	593 ms 88,052 KB
testcase_203	AC	376 ms 71,936 KB
testcase_204	AC	870 ms 93,048 KB
testcase_205	AC	388 ms 72,432 KB
testcase_206	AC	351 ms 90,092 KB
testcase_207	AC	215 ms 62,564 KB
testcase_208	AC	602 ms 87,552 KB
testcase_209	AC	267 ms 68,372 KB
testcase_210	AC	170 ms 60,696 KB
testcase_211	AC	357 ms 71,232 KB
testcase_212	AC	173 ms 61,656 KB
testcase_213	AC	242 ms 71,568 KB
testcase_214	AC	787 ms 92,744 KB
testcase_215	AC	560 ms 90,448 KB
testcase_216	WA	-
testcase_217	WA	-
testcase_218	AC	260 ms 62,908 KB
testcase_219	AC	250 ms 72,208 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

結果

テストケース

ソースコード