結果
問題 | No.1767 BLUE to RED |
ユーザー |
![]() |
提出日時 | 2021-11-26 22:41:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 899 bytes |
コンパイル時間 | 637 ms |
コンパイル使用メモリ | 72,268 KB |
実行使用メモリ | 12,900 KB |
最終ジャッジ日時 | 2024-06-29 18:17:03 |
合計ジャッジ時間 | 4,324 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <algorithm> #include <iostream> using namespace std; typedef long long ll; typedef pair<ll, int> P; const ll INF = 100000000000; ll dp[200002][2]; int main() { int n, m; cin >> n >> m; P p[400002]; for(int i = 0; i < n; i++){ ll a; cin >> a; p[i] = P(a, 0); } for(int i = 0; i < m; i++){ ll b; cin >> b; p[i + n] = P(b, 1); } p[n + m] = P(-INF, 0); sort(p, p + n + m + 1); int c = 0; for(int i = 1; i <= n + m; i++){ if(p[i].second){ c++; dp[c][0] = dp[c - 1][0] + p[i].first - p[i - 1].first; dp[c][1] = min(dp[c - 1][1] + p[i].first - p[i - 1].first, dp[c - 1][0]); } else{ dp[c][0] = min(dp[c][0], dp[c][1] + p[i].first - p[i - 1].first); dp[c][1] = dp[c][0]; } } cout << dp[c][0] << endl; }