#include #include #include #define TOTAL_MASTS 3 //function definitions int SailsComparison(const void* a, const void* b); int compare_longs(const void* a, const void* b); int upper_bound(long long arr[], int n, long long value); //struct definitions typedef struct { long long h; long long area; int mast_index; int rank; } StructSail; typedef struct { int n; long long s; long long* h; long long* maximumDPprefixes; } Mast; int SailsComparison(const void* a, const void* b) { StructSail* sail_a = (StructSail*)a; StructSail* sail_b = (StructSail*)b; if (sail_a->h < sail_b->h) return -1; if (sail_a->h > sail_b->h) return 1; return 0; } //For qsort int compare_longs(const void* a, const void* b) { long long val_a = *(const long long*)a; long long val_b = *(const long long*)b; if (val_a < val_b) return -1; if (val_a > val_b) return 1; return 0; } //This could possibly help address is used to perform an extremely fast binary search int upper_bound(long long arr[], int n, long long value) { int low = 0, high = n; while (low < high) { int mid = low + (high - low) / 2; if (arr[mid] <= value) { low = mid + 1; } else { high = mid; } } return low; } int main() { // Reading input long long d; scanf("%lld", &d); Mast masts[TOTAL_MASTS]; int total_sails = 0; for (int i = 0; i < TOTAL_MASTS; ++i) { scanf("%d %lld", &masts[i].n, &masts[i].s); masts[i].h = (long long*) malloc (masts[i].n * sizeof(long long)); for (int j = 0; j < masts[i].n; ++j) { scanf("%lld", &masts[i].h[j]); } qsort(masts[i].h, masts[i].n, sizeof(long long), compare_longs); total_sails += masts[i].n; } StructSail* SailsWithUs = (StructSail*)malloc(total_sails * sizeof(StructSail)); int k = 0; for (int i = 0; i < TOTAL_MASTS; ++i) { for (int j = 0; j < masts[i].n; ++j) { SailsWithUs[k].h = masts[i].h[j]; SailsWithUs[k].mast_index = i; SailsWithUs[k].area = masts[i].s * masts[i].s; SailsWithUs[k].rank = j; // The rank after sorting within the mast k++; } } //Assuming that there are n heights, but not that they will be in any particular order. qsort(SailsWithUs, total_sails, sizeof(StructSail), SailsComparison); for (int i = 0; i < TOTAL_MASTS; i++) { masts[i].maximumDPprefixes = (long long*)calloc(masts[i].n, sizeof(long long)); } long long TotalAreaOptimized = 0; for (int i = 0; i < total_sails; ++i) { StructSail current_sail = SailsWithUs[i]; long long h_i = current_sail.h; int m_i = current_sail.mast_index; long long s_i = masts[m_i].s; long long max_prev_dp = 0; for (int m_j = 0; m_j < TOTAL_MASTS; ++m_j) { long long s_j = masts[m_j].s; long long HeightLimit; int num_potential; if (m_i == m_j) { HeightLimit = h_i - s_i; } else if (abs(m_i - m_j) == 1) { long long K = s_i + s_j - d; if (K > 0) { HeightLimit = h_i - K -1; // -1 for strict inequality } else { HeightLimit = h_i; } } else { HeightLimit = h_i; } num_potential = upper_bound(masts[m_j].h, masts[m_j].n, HeightLimit); if (num_potential > 0) { long long DP_Intermediate = masts[m_j].maximumDPprefixes[num_potential - 1]; if (DP_Intermediate > max_prev_dp) { max_prev_dp = DP_Intermediate; } } } long long current_dp = current_sail.area + max_prev_dp; int rank = current_sail.rank; long long prev_max = (rank > 0) ? masts[m_i].maximumDPprefixes[rank - 1] : 0; masts[m_i].maximumDPprefixes[rank] = (current_dp > prev_max) ? current_dp : prev_max; if (current_dp > TotalAreaOptimized) { TotalAreaOptimized = current_dp; } } printf("%lld\n", TotalAreaOptimized); for (int i = 0; i < TOTAL_MASTS; ++i) { free(masts[i].h); free(masts[i].maximumDPprefixes); } free(SailsWithUs); return 0; }