#include #include #include #include // Incorrect solution (same concept as "semigreedy") generated via prompt. /* Here's the approach: Conflict Analysis: First, I determined the precise condition for when two sails overlap. A sail on mast A at height h_A and a sail on mast B at height h_B conflict if and only if d - 2*s_B <= h_A - h_B <= 2*s_A - d, where d is the distance between masts and s_A, s_B are the sail sizes. A similar condition applies between masts B and C. Sails on the same mast conflict if the difference in their attachment heights is less than the sail size for that mast. DP on Mast B: The problem can be solved with dynamic programming by processing the potential sail positions on the middle mast (B) in increasing order of height. Let dp[i] be the maximum possible propulsion area considering a valid arrangement where the highest sail on mast B is placed at position b_i. State Transition: To compute dp[i], we consider that we are placing a sail at b_i. This gives us an area of s_B^2. We then need to add the maximum possible area from: Other sails on mast B at heights b_j such that b_j <= b_i - s_B. This is found by taking the maximum over previous dp[j] values. Sails on mast A and mast C. The set of chosen sails on mast B creates "forbidden" vertical zones on masts A and C. We calculate the maximum area we can get from the remaining "allowed" zones. Optimization: A naive DP would be too slow. The key challenge is efficiently calculating the maximum area on masts A and C for different sets of B-sails. I've structured the solution to pre-calculate values for individual masts and then use a DP approach that iterates through the choices for the middle mast, finding the optimal compatible arrangement. The final implementation simplifies this logic to iterate through each potential sail on mast B as the "anchor" for a configuration, leading to an effective, albeit complex, solution. */ 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 for (ll height : mast.h) { if (height >= min_h && height <= max_h) { relevant_heights.push_back(height); } } 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. 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; } 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 chosen is from the subset {b_1, ..., b_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]; // Find the best previous compatible B-sail configuration ll max_prev_dp = 0; int best_p = -1; auto it = upper_bound(mast_B.h.begin(), mast_B.h.begin() + i, h_b - mast_B.s); if (it != mast_B.h.begin()) { int p_limit = distance(mast_B.h.begin(), it) - 1; for(int p=0; p <= p_limit; ++p) { if (dp[p] > max_prev_dp) { max_prev_dp = dp[p]; best_p = p; } } } // Form the current set of B-sails vector current_H_B; if (best_p != -1) { current_H_B = H_B_sets[best_p]; } current_H_B.push_back(h_b); // Calculate forbidden intervals on A and C for this set of B-sails vector> forbidden_A, forbidden_C; if (d <= mast_A.s + mast_B.s) { for (ll b_h : current_H_B) { 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 : current_H_B) { 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)current_H_B.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); dp[i] = b_area + a_area + c_area; H_B_sets[i] = current_H_B; } ll max_total_area = 0; // The optimal solution might not use any B-sails max_total_area = solve_mast_with_forbidden(mast_A, {}) + solve_mast_with_forbidden(mast_C, {}); // The optimal solution could be any of the DP states for (ll val : dp) { max_total_area = max(max_total_area, val); } cout << max_total_area << endl; return 0; }