fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8. #define all(v) v.begin(),v.end()
  9. #define sz(s) (int)(s).size()
  10. #define ll long long
  11. #define ld long double
  12. #define el "\n"
  13. #define PI  3.141592653589793
  14. #define fx(x) fixed<<setprecision(x)
  15. #define F first
  16. #define S second
  17. #define memo(mem, val) memset(mem, val, sizeof(mem))
  18. #define IOS ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  19.  
  20. void File() {
  21. #ifndef ONLINE_JUDGE
  22.     freopen("input.txt", "r", stdin);
  23.     freopen("output.txt", "w", stdout);
  24. #endif
  25. }
  26.  
  27. const int N = 2e3 + 5;
  28. int n, k, p;
  29. vector<int> a, b;
  30. priority_queue<tuple<ll, int, int>> pq;
  31.  
  32. ll calc(int i, int j) {
  33.     return abs(a[i] - b[j]) + abs(b[j] - k);
  34. }
  35. bool can(ll mid) {
  36.     priority_queue<tuple<ll, int, int>> tmp = pq;
  37.     vector<int> vis_p(N), vis_k(N);
  38.     int pr = 0;
  39.     while (!tmp.empty()) {
  40.         auto [cost, i, j] = tmp.top();
  41.         tmp.pop();
  42.         if (vis_p[i] || vis_k[j] || cost > mid)continue;
  43.         pr++;
  44.         vis_p[i] = vis_k[j] = 1;
  45.     }
  46.     return (pr == n);
  47. }
  48. void solve() {
  49.     cin >> n >> k >> p;
  50.     a = vector<int>(n), b = vector<int>(k);
  51.     for (auto &i: a)cin >> i;
  52.     for (auto &i: b)cin >> i;
  53.     for (int i = 0; i < n; ++i) {
  54.         for (int j = 0; j < k; ++j) {
  55.             pq.push({calc(i, j), i, j});
  56.         }
  57.     }
  58.     ll l = 0, r = 1e18, ans;
  59.     while (l <= r) {
  60.         ll mid = (l + r) / 2;
  61.         if (can(mid)) {
  62.             ans = mid;
  63.             r = mid - 1;
  64.         }
  65.         else l = mid + 1;
  66.     }
  67.     cout << ans;
  68.  
  69. }
  70.  
  71. int main() {
  72.     IOS
  73.     File();
  74.     int tc = 1;
  75.     //cin >> tc;
  76.     for (int i = 1; i <= tc; ++i) {
  77.         solve();
  78.         if (i < tc) cout << "\n";
  79.     }
  80.  
  81.     return 0;
  82. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/28Q1YL
language:
C++14 (gcc 8.3)
created:
18 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!