Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma warning (disable : 4996)
- #include <stdlib.h>
- #include <iostream>
- #include <vector>
- #include <string>
- #include <assert.h>
- #include <stack>
- #include <algorithm>
- #include <ios>
- #include <iostream>
- #include <fstream>
- #include <iomanip>
- #include <queue>
- #include <set>
- #include <functional>
- #include <cmath>
- #include <sstream>
- #include <map>
- #include <memory.h>
- #include <stdio.h>
- #include <cassert>
- #include <string.h>
- #include <unordered_map>
- #define forn(i , n) for (int i = 0; i < n; ++i)
- #define down(i, n) for (int i = n - 1; i >= 0; --i)
- using namespace std;
- typedef unsigned long long int u64;
- typedef long long int i64;
- typedef vector<i64> vint;
- typedef vector<i64> vi64;
- typedef pair<int, int> pint;
- typedef pair<i64, i64> pi64;
- #define FILE_NAME "file"
- struct Node
- {
- vector<i64> nbr;
- i64 x, y;
- i64 used;
- i64 best;
- i64 what;
- Node()
- {
- used = 0;
- best = 1000000000000000LL;
- }
- };
- struct Comp
- {
- i64 n;
- i64 t;
- i64 p;
- bool operator<(const Comp & b) const
- {
- return p < b.p;
- }
- };
- const i64 inf = 1000000000000LL;
- void calc(vector<Comp> & s, vector<Comp> & t, i64 j, i64 b, i64 & bNumb, i64 & p)
- {
- i64 i = 0;
- p = 0;
- bNumb = 0;
- while (b > 0)
- {
- if (i < s.size())
- {
- if (j < t.size())
- {
- if (s[i] < t[j])
- {
- p += s[i].p;
- ++i;
- }
- else
- {
- p += t[j].p;
- ++j;
- }
- }
- else
- {
- p += s[i].p;
- ++i;
- }
- }
- else if (j < t.size())
- {
- p += t[j].p;
- ++j;
- }
- else
- {
- break;
- }
- bNumb++;
- --b;
- }
- }
- void calcPrint(vector<Comp> & s, vector<Comp> & t, i64 j, i64 b, i64 & bNumb, i64 & p, i64 from)
- {
- i64 i = 0;
- p = 0;
- bNumb = 0;
- i64 n = from;
- while (b > 0)
- {
- if (i < s.size())
- {
- if (j < t.size())
- {
- if (s[i] < t[j])
- {
- p += s[i].p;
- cout << s[i].n << " " << from << "\n";
- ++from;
- ++i;
- }
- else
- {
- p += t[j].p;
- cout << t[j].n << " " << from << "\n";
- ++from;
- ++j;
- }
- }
- else
- {
- p += s[i].p;
- cout << s[i].n << " " << from << "\n";
- ++from;
- ++i;
- }
- }
- else if (j < t.size())
- {
- p += t[j].p;
- cout << t[j].n << " " << from << "\n";
- ++from;
- ++j;
- }
- else
- {
- break;
- }
- bNumb++;
- --b;
- }
- }
- struct Scene
- {
- double x;
- double bestL, bestR;
- i64 n;
- bool operator<(const Scene & b) const
- {
- return x < b.x;
- }
- };
- bool cmp(const Scene& a, const Scene & b)
- {
- return a.n < b.n;
- }
- i64 R;
- bool check(double x, double y)
- {
- double d = fabs(x - y);
- d *= d;
- if (R*R < d + 1)
- {
- return false;
- }
- return true;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout << fixed << setprecision(15);
- #ifdef FILE_INPUT
- freopen(FILE_NAME ".in", "r", stdin);
- freopen(FILE_NAME ".out", "w", stdout);
- #endif
- i64 n = 0;
- i64 m = 0;
- cin >> m >> n;
- cin >> R;
- vector<double> c(m);
- vector<Scene> s(n);
- forn(i, m)
- {
- cin >> c[i];
- }
- forn(i, n)
- {
- cin >> s[i].x;
- s[i].n = i;
- }
- sort(s.begin(), s.end());
- i64 l = 0, r = 0;
- forn(i, n)
- {
- while (!check(s[i].x, c[l]))
- {
- ++l;
- }
- s[i].bestL = c[l];
- r = max(l, r);
- while (r + 1 < m && check(s[i].x, c[r + 1]))
- {
- ++r;
- }
- s[i].bestR = c[r];
- }
- sort(s.begin(), s.end(), cmp);
- double currPos = c[0];
- double ans = 0;
- forn(i, n)
- {
- if (currPos >= s[i].bestL && currPos <= s[i].bestR)
- {
- continue;
- }
- else
- {
- if (fabs(s[i].bestL - currPos) < fabs(s[i].bestR - currPos))
- {
- ans += fabs(s[i].bestL - currPos);
- currPos = s[i].bestL;
- }
- else
- {
- ans += fabs(s[i].bestR - currPos);
- currPos = s[i].bestR;
- }
- }
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement