結果
問題 |
No.2759 Take Pictures, Elements?
|
ユーザー |
![]() |
提出日時 | 2024-10-21 18:34:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,548 bytes |
コンパイル時間 | 1,735 ms |
コンパイル使用メモリ | 206,664 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2025-06-20 13:21:55 |
合計ジャッジ時間 | 2,812 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll N, Q, i, j, ni, nj, alt, C; cin >> N >> Q; vector<ll> A(N+1), B(Q+1); for (int i=1; i<=N; i++) cin >> A[i]; for (int i=1; i<=Q; i++) cin >> B[i]; /* dist(i, j) = 箱iを参照している状態でj枚目までの写真を撮るまでの最小ステップ数 */ deque<pair<ll, ll>> que; vector dist(N+1, vector<ll>(Q+1, 1e18)); dist[1][0] = 0; que.push_back({1,0}); while(!que.empty()){ tie(i, j) = que.front(); que.pop_front(); if (i <= N-1){ ni = i+1; nj = j; C = 1; alt = dist[i][j]+C; if (alt<dist[ni][nj]){ dist[ni][nj] = alt; que.push_back({ni, nj}); } } if (2 <= i){ ni = i-1; nj = j; C = 1; alt = dist[i][j]+C; if (alt<dist[ni][nj]){ dist[ni][nj] = alt; que.push_back({ni, nj}); } } if (j+1<=Q && A[i] == B[j+1]){ ni = i; nj = j+1; C = 0; alt = dist[i][j]+C; if (alt<dist[ni][nj]){ dist[ni][nj] = alt; que.push_front({ni, nj}); } } } ll ans = 1e18; for (int i=1; i<=N; i++) ans = min(ans, dist[i][Q]); cout << ans << endl; return 0; }