Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <climits>
- #include <string>
- #include <set>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <numeric>
- #include <random>
- #include <memory>
- #include <chrono>
- #include <iterator>
- #include <functional>
- #include <unordered_set>
- #include <cassert>
- #ifdef LOCAL
- #include "debug.h"
- #else
- #define debug(x...)
- #endif
- //#pragma GCC optimize("Ofast")
- //#define int ll
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair <int, int> pii;
- #define mp make_pair
- #define pb push_back
- #define sz(x) int((x).size())
- #ifndef LOCAL
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(228);
- #endif
- const int N = 2e3 + 7;
- const int inf = INT_MAX / 2;
- const ll INF = LLONG_MAX / 3;
- const int MOD = 1e9 + 7;
- const double eps = 1e-6;
- const string cars[] = {"🚗", "🚕", "🚙"};
- struct sparse {
- private: vector < vector < float > > a;
- private: short log;
- private: int flog(int x) {
- return 32 - __builtin_clz(x) - 1;
- }
- public: sparse(vector < float >& v) {
- log = ceil(flog(sz(v)));
- a = vector < vector < float > > (sz(v), vector < float > (log + 1));
- for (int i = 0; i < sz(v); i++) {
- a[i][0] = v[i];
- }
- for (int j = 1; j <= log; j++) {
- for (int i = sz(v) - 1; i >= 0; i--) {
- if (i + (1 << (j - 1)) < sz(a)) {
- a[i][j] = min(a[i + (1 << (j - 1))][j - 1], a[i][j - 1]);
- }
- }
- }
- }
- public: sparse() {}
- public: float query(int l, int r) {
- int j = flog(r - l + 1);
- return min(a[l][j], a[r - (1 << j) + 1][j]);
- }
- };
- int a[N], b[N];
- float f[N][N];
- sparse F[2 * N];
- float check(int k, int w, short n, short m) {
- float ans = INF;
- for (short i = 0; i < n; i++) {
- for (short j = 0; j < m; j++) {
- short xy = k + i + j - 2;
- short xs = min(max(i, short(xy - m + 1)), short(n - 1));
- short xf = min(n - 1, xy - j);
- if (xs > xf || xy > n + m - 2) {
- continue;
- }
- ans = min(ans, F[xy].query(xs, xf) + 2 * float(sqrt(1LL * (a[i] - b[j]) * (a[i] - b[j]) + w * w)) - f[i][j]);
- }
- }
- return ans;
- }
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(9);
- ios::sync_with_stdio(false);
- cin.tie();
- cout.tie();
- int l, w, n, m;
- cin >> l >> w >> n;
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- }
- cin >> m;
- for (int i = 0; i < m; i++) {
- cin >> b[i];
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- f[i][j] = a[i] + b[j] + w + sqrt(1LL * (b[j] - a[i]) * (b[j] - a[i]) + w * w);
- }
- }
- for (int j = 0; j < m; j++) {
- int x = 0, y = j;
- vector < float > t;
- for (; x < n && y >= 0; x++, y--) {
- t.push_back(f[x][y]);
- }
- F[j] = sparse(t);
- }
- for (int j = m; j < n + m - 1; j++) {
- int x = j - m + 1, y = m - 1;
- vector < float > t;
- for (; x < n && y >= 0; x++, y--) {
- t.push_back(f[x][y]);
- }
- reverse(t.begin(), t.end());
- while (sz(t) < x) {
- t.push_back(INF);
- }
- reverse(t.begin(), t.end());
- F[j] = sparse(t);
- }
- if (check(2, w, n, m) > l) {
- return cout << 0, 0;
- }
- int left = 2, right = n + m + 1;
- while (right - left > 1) {
- int mid = (left + right) / 2;
- if (check(mid, w, n, m) < l) {
- left = mid;
- }
- else {
- right = mid;
- }
- }
- cout << (check(right, w, n, m) > l ? left : right);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement