Advertisement
999ms

Untitled

Apr 15th, 2020
403
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) begin(x),end(x)
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. const int N = 200200;
  7.  
  8. ll f(int a, int b) {
  9.   return (a - b) * 1ll * (a - b);
  10. }
  11.  
  12. ll f(int a, int b, int c) {
  13.   return f(a, b) + f(a, c) + f(b, c);
  14. }
  15.  
  16. ll solve(vector<int>& a, vector<int>& b, vector<int>& c) {
  17.   ll ans = 5e18;
  18.   int j = 0;
  19.   int k = 0;
  20.   for (int i = 0; i < size(a); i++) {
  21.     while (j < size(b) && b[j] < a[i]) j++;
  22.     if (j < size(b)) {
  23.       k = max(0, k - 1);
  24.       ll pre = f(a[i], b[j], c[k]);
  25.       ll cur = pre;
  26.       ans = min(ans, pre);
  27.       while (k < size(c)) {
  28.         cur = f(a[i], b[j], c[k]);
  29.         if (cur > pre) break;
  30.         ans = min(ans, cur);
  31.         pre = cur;
  32.         k++;
  33.       }
  34.     } else {
  35.       break;
  36.     }
  37.   }
  38.   return ans;
  39. }
  40.  
  41. void solve() {
  42.   int a, b, c;
  43.   cin >> a >> b >> c;
  44.   vector<int> arr(a), brr(b), crr(c);
  45.   for (int i = 0; i < a; i++) cin >> arr[i];
  46.   for (int i = 0; i < b; i++) cin >> brr[i];
  47.   for (int i = 0; i < c; i++) cin >> crr[i];
  48.   sort(all(arr));
  49.   sort(all(brr));
  50.   sort(all(crr));
  51.   ll ans = 5e18;
  52.   ans = min(ans, solve(arr, brr, crr));
  53.   ans = min(ans, solve(arr, crr, brr));
  54.   ans = min(ans, solve(brr, crr, arr));
  55.   ans = min(ans, solve(brr, arr, crr));
  56.   ans = min(ans, solve(crr, arr, brr));
  57.   ans = min(ans, solve(crr, brr, arr));
  58.   cout << ans << '\n';
  59. }
  60.  
  61.  
  62. int main() {
  63.   ios_base::sync_with_stdio(false);
  64.   cin.tie(nullptr);
  65.   cout.tie(nullptr);
  66.   int t;
  67.   cin >> t;
  68.   while (t--) {
  69.     solve();
  70.   }
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement