#include #include #include #include using namespace std; typedef long long ll; // Structure to hold information about a mast struct Mast { int id; int n; ll s; vector h; ll s_sq; }; // Memoization table for calculate_max_sails map, ll> memo[3]; // Calculates max number of sails for a given list of heights and sail size within a specific range [min_h, max_h]. // It uses dynamic programming with memoization to avoid recomputing results for the same range. ll calculate_max_sails(const Mast& mast, ll min_h, ll max_h) { if (min_h > max_h) { return 0; } if (memo[mast.id].count({min_h, max_h})) { return memo[mast.id][{min_h, max_h}]; } vector relevant_heights; // Extract heights within the given range auto lower = lower_bound(mast.h.begin(), mast.h.end(), min_h); auto upper = upper_bound(mast.h.begin(), mast.h.end(), max_h); for (auto it = lower; it != upper; ++it) { relevant_heights.push_back(*it); } if (relevant_heights.empty()) { return 0; } int num_heights = relevant_heights.size(); vector dp(num_heights, 0); // dp[i] = max number of sails using a subset of the first i+1 relevant heights dp[0] = 1; for (int i = 1; i < num_heights; ++i) { ll current_h = relevant_heights[i]; // Option 1: Don't place a sail at current_h. The max is the result from the previous height. ll dont_place = dp[i - 1]; // Option 2: Place a sail at current_h. ll place = 1; // Find the highest previous sail that doesn't overlap. auto it = upper_bound(relevant_heights.begin(), relevant_heights.begin() + i, current_h - mast.s); if (it != relevant_heights.begin()) { int p = distance(relevant_heights.begin(), it) - 1; place += dp[p]; } dp[i] = max(place, dont_place); } return memo[mast.id][{min_h, max_h}] = dp.back(); } // Calculates the maximum area on a mast given a set of forbidden height intervals. ll solve_mast_with_forbidden(const Mast& mast, const vector>& forbidden_intervals) { if (mast.n == 0) return 0; vector> merged_forbidden; if (!forbidden_intervals.empty()) { // Merge overlapping forbidden intervals to simplify calculation merged_forbidden.push_back(forbidden_intervals[0]); for (size_t i = 1; i < forbidden_intervals.size(); ++i) { if (forbidden_intervals[i].first <= merged_forbidden.back().second) { merged_forbidden.back().second = max(merged_forbidden.back().second, forbidden_intervals[i].second); } else { merged_forbidden.push_back(forbidden_intervals[i]); } } } ll total_sails = 0; ll last_h = -1; // Start from lowest possible height // Sum up sails from all allowed intervals for (const auto& interval : merged_forbidden) { total_sails += calculate_max_sails(mast, last_h + 1, interval.first - 1); last_h = interval.second; } // Add sails from the last allowed interval (from the last forbidden point to infinity) total_sails += calculate_max_sails(mast, last_h + 1, 20000000 + 100); return total_sails * mast.s_sq; } // Helper to calculate total area given a set of B-sails ll calculate_total_area(const vector& h_b_set, const Mast& mast_A, const Mast& mast_B, const Mast& mast_C, ll d) { if (h_b_set.empty()) { return solve_mast_with_forbidden(mast_A, {}) + solve_mast_with_forbidden(mast_C, {}); } vector> forbidden_A, forbidden_C; if (d <= mast_A.s + mast_B.s) { for (ll b_h : h_b_set) { forbidden_A.push_back({b_h + d - 2 * mast_B.s, b_h + 2 * mast_A.s - d}); } } if (d <= mast_B.s + mast_C.s) { for (ll b_h : h_b_set) { forbidden_C.push_back({b_h - 2 * mast_B.s + d, b_h - d + 2 * mast_C.s}); } } sort(forbidden_A.begin(), forbidden_A.end()); sort(forbidden_C.begin(), forbidden_C.end()); ll b_area = (ll)h_b_set.size() * mast_B.s_sq; ll a_area = solve_mast_with_forbidden(mast_A, forbidden_A); ll c_area = solve_mast_with_forbidden(mast_C, forbidden_C); return a_area + b_area + c_area; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll d; cin >> d; Mast masts[3]; for (int i = 0; i < 3; ++i) { masts[i].id = i; cin >> masts[i].n >> masts[i].s; masts[i].h.resize(masts[i].n); masts[i].s_sq = masts[i].s * masts[i].s; for (int j = 0; j < masts[i].n; ++j) { cin >> masts[i].h[j]; } sort(masts[i].h.begin(), masts[i].h.end()); } Mast& mast_A = masts[0]; Mast& mast_B = masts[1]; Mast& mast_C = masts[2]; // dp[i] stores the max total area for a valid configuration where the highest B-sail is at mast_B.h[i]. vector dp(mast_B.n, 0); // H_B_sets[i] stores the actual set of B-sail heights for the optimal solution at dp[i]. vector> H_B_sets(mast_B.n); for (int i = 0; i < mast_B.n; ++i) { ll h_b = mast_B.h[i]; // Base case: sail at h_b is the only one on mast B. vector base_H_B = {h_b}; ll max_area_for_i = calculate_total_area(base_H_B, mast_A, mast_B, mast_C, d); vector best_H_B_for_i = base_H_B; // Find best compatible preceding configuration to extend. for (int p = 0; p < i; ++p) { if (mast_B.h[p] <= h_b - mast_B.s) { // We can potentially extend the configuration ending at p. vector new_H_B = H_B_sets[p]; new_H_B.push_back(h_b); ll current_area = calculate_total_area(new_H_B, mast_A, mast_B, mast_C, d); if (current_area > max_area_for_i) { max_area_for_i = current_area; best_H_B_for_i = new_H_B; } } } dp[i] = max_area_for_i; H_B_sets[i] = best_H_B_for_i; } // The overall max area is the max of all dp[i] values, // plus the case where no B-sails are used. ll max_total_area = calculate_total_area({}, mast_A, mast_B, mast_C, d); for (ll val : dp) { max_total_area = max(max_total_area, val); } cout << max_total_area << endl; return 0; }