結果
問題 |
No.2759 Take Pictures, Elements?
|
ユーザー |
![]() |
提出日時 | 2024-05-17 21:42:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,817 bytes |
コンパイル時間 | 1,309 ms |
コンパイル使用メモリ | 138,280 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-06-20 13:16:53 |
合計ジャッジ時間 | 2,008 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <array> #include <iterator> #include <string> #include <cctype> #include <cstring> #include <cstdlib> #include <cassert> #include <cmath> #include <ctime> #include <iomanip> #include <numeric> #include <stack> #include <queue> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <bitset> #include <random> #include <utility> #include <functional> #include <chrono> using namespace std; void Main() { int N,Q; cin >> N >> Q; vector<int> A(N),B(Q); vector<int> comp; comp.reserve(N + Q); for(int i = 0;i < N;i++) { cin >> A[i]; comp.push_back(A[i]); } for(int i = 0;i < Q;i++) { cin >> B[i]; comp.push_back(B[i]); } sort(comp.begin(),comp.end()); comp.erase(unique(comp.begin(),comp.end()), comp.end()); vector<vector<int>> G(comp.size() + 1); for(int i = 0;i < N;i++) { int id = lower_bound(comp.begin(),comp.end(),A[i]) - comp.begin(); G[id].push_back(i); } G[comp.size()].push_back(0); int cur = comp.size(); vector<int> dp(1, 0); for(int q = 0;q < Q;q++) { int nxt = lower_bound(comp.begin(),comp.end(), B[q]) - comp.begin(); vector<int> n_dp(G[nxt].size(), (int)1e9); int j = 0; for(int i = 0;i < (int)G[nxt].size();i++) { while(j < G[cur].size() && G[cur][j] < G[nxt][i]) { j++; } if(j > 0) { n_dp[i] = min(n_dp[i], dp[j - 1] + G[nxt][i] - G[cur][j - 1]); } if(j < (int)G[cur].size()) { n_dp[i] = min(n_dp[i], dp[j] + G[cur][j] - G[nxt][i]); } } swap(n_dp,dp); swap(nxt, cur); } int ans = (int)1e9; for(int i = 0;i < (int)dp.size();i++) { ans = min(ans, dp[i]); } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; /* cin >> tt; */ while(tt--) Main(); }