#1004779 (cLay) No.2855 Move on Grid

• 問題: No.2855 Move on Grid
• ユーザー: tails
• 提出日時: 2024-08-25 15:20:43
• 言語: cLay (20240714-1)
• 結果: AC
• 実行時間: 290 ms / 3,000 ms
• コード長: 480 bytes
• コンパイル時間: 3,242 ms
• コンパイル使用メモリ: 176,960 KB
• 実行使用メモリ: 9,028 KB
• 最終ジャッジ日時: 2024-08-25 15:20:56
• 合計ジャッジ時間: 11,270 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	63 ms; 6,816 KB
testcase_01	AC	78 ms; 6,944 KB
testcase_02	AC	49 ms; 6,940 KB
testcase_03	AC	37 ms; 6,940 KB
testcase_04	AC	27 ms; 6,944 KB
testcase_05	AC	59 ms; 6,940 KB
testcase_06	AC	59 ms; 6,940 KB
testcase_07	AC	7 ms; 6,940 KB
testcase_08	AC	43 ms; 6,940 KB
testcase_09	AC	20 ms; 6,940 KB
testcase_10	AC	188 ms; 6,940 KB
testcase_11	AC	214 ms; 7,364 KB
testcase_12	AC	189 ms; 6,948 KB
testcase_13	AC	194 ms; 6,940 KB
testcase_14	AC	193 ms; 6,940 KB
testcase_15	AC	188 ms; 7,496 KB
testcase_16	AC	188 ms; 6,944 KB
testcase_17	AC	215 ms; 6,944 KB
testcase_18	AC	184 ms; 9,028 KB
testcase_19	AC	189 ms; 7,368 KB
testcase_20	AC	254 ms; 6,940 KB
testcase_21	AC	244 ms; 6,944 KB
testcase_22	AC	254 ms; 6,940 KB
testcase_23	AC	290 ms; 6,944 KB
testcase_24	AC	240 ms; 7,236 KB
testcase_25	AC	244 ms; 7,364 KB
testcase_26	AC	250 ms; 6,940 KB
testcase_27	AC	276 ms; 6,944 KB
testcase_28	AC	256 ms; 6,944 KB
testcase_29	AC	247 ms; 6,940 KB
testcase_30	AC	246 ms; 7,624 KB
testcase_31	AC	240 ms; 6,944 KB
testcase_32	AC	272 ms; 6,940 KB
testcase_33	AC	260 ms; 6,940 KB
testcase_34	AC	231 ms; 6,940 KB
testcase_35	AC	251 ms; 6,940 KB
testcase_36	AC	214 ms; 6,940 KB
testcase_37	AC	260 ms; 6,944 KB
testcase_38	AC	247 ms; 6,944 KB
testcase_39	AC	241 ms; 6,944 KB

ソースコード

DijkstraHeap<int>h;
int@n,@m,@k,@a[n][m];
h.malloc(9d4);
int ok=1,ng=1d9+1;
while(ok+1<ng){
	int t=ok+ng>>1;
	h.init(9d4);
	h.change(0,a[0][0]<t);
	while(h.size){
		int i=h.pop();
		int v=h.val[i];
		int y=i/300;
		int x=i%300;
		if(y)     h.change(i-300,v+(a[y-1][x]<t));
		if(y<n-1) h.change(i+300,v+(a[y+1][x]<t));
		if(x)     h.change(i-  1,v+(a[y][x-1]<t));
		if(x<m-1) h.change(i+  1,v+(a[y][x+1]<t));
	}
	if(h.val[(n-1)*300+(m-1)]<=k){
		ok=t;
	}else{
		ng=t;
	}
}
wt(ok);