結果
問題 | No.2673 A present from B |
ユーザー |
|
提出日時 | 2024-03-16 00:25:18 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 768 ms / 2,000 ms |
コード長 | 1,397 bytes |
コンパイル時間 | 3,604 ms |
コンパイル使用メモリ | 180,072 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 03:35:44 |
合計ジャッジ時間 | 8,019 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import std; void main () { int N, M; readln.read(N, M); auto A = readln.split.to!(int[]); auto dp = new int[][](M + 1, N + 1); int[] ans; BinaryHeap!(Tuple!(int, int)[], "b[1] < a[1]") PQ = []; foreach (bob; 2..N+1) { foreach (d; dp) d[] = int.max; for (int i = 0; bob + i <= N; i++) dp[0][bob + i] = i; for (int i = 0; 1 <= bob - i; i++) dp[0][bob - i] = i; foreach (i; 0..M) { dp[i + 1][] = dp[i][]; // 操作 dp[i + 1][A[i] + 1] = dp[i][A[i]]; dp[i + 1][A[i]] = dp[i][A[i] + 1]; // 右となり int mn = 1 << 30; for (int j = 0; j < N; j++) { dp[i + 1][j] = min(dp[i + 1][j], mn); mn = min(mn, dp[i + 1][j]); mn++; } // 左となり mn = 1 << 30; for (int j = N - 1; j >= 0; j--) { dp[i + 1][j] = min(dp[i + 1][j], mn); mn = min(mn, dp[i + 1][j]); mn++; } } ans ~= dp[M][1]; } foreach (i, a; ans) { write(a, i == ans.length - 1 ? '\n' : ' '); } } void read (T...) (string S, ref T args) { import std.conv : to; import std.array : split; auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } }