結果
問題 |
No.2759 Take Pictures, Elements?
|
ユーザー |
![]() |
提出日時 | 2024-05-17 21:47:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 1,161 bytes |
コンパイル時間 | 714 ms |
コンパイル使用メモリ | 86,968 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-06-20 13:17:03 |
合計ジャッジ時間 | 1,577 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; auto all = a; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); int siz = all.size(); vector<vector<int>> id(siz); for (int i = 0; i < n; ++i) { int idx = lower_bound(all.begin(), all.end(), a[i]) - all.begin(); id[idx].push_back(i); } vector<int> dp(n, 1e9); dp[0] = 0; while (q--) { int b; cin >> b; int idx = lower_bound(all.begin(), all.end(), b) - all.begin(); vector<int> ndp(n, 1e9); for (int i = 0; i < n; ++i) { int id2 = lower_bound(id[idx].begin(), id[idx].end(), i) - id[idx].begin(); int li = -1, ri = -1; if (id2 < id[idx].size()) ri = id[idx][id2]; --id2; if (id2 >= 0) li = id[idx][id2]; if (li >= 0) ndp[li] = min(ndp[li], dp[i] + abs(li - i)); if (ri < n) ndp[ri] = min(ndp[ri], dp[i] + abs(ri - i)); } swap(ndp, dp); } int ans = 1e9; for (int i = 0; i < n; ++i) ans = min(ans, dp[i]); cout << ans << endl; }