Overview

Given \(N\) observation spots, the problem asks to build suspension bridges between \(K\) adjacent pairs and maximize the total sum of absolute differences in elevation (thrill value). You need to optimally determine both the arrangement order of the observation spots and the placement of the suspension bridges.

Analysis

1. Optimal Strategy for Placing Suspension Bridges

We consider how to place the suspension bridges to maximize the total elevation difference. When we connect the locations where bridges are placed, several “paths (traversal routes)” are formed. In general, when maximizing the sum of absolute differences between adjacent elements, a vertex inside a path (degree 2) is connected to both neighbors, so it can contribute at most \(+2\) times (or \(-2\) times) its elevation. On the other hand, a vertex at the end of a path (degree 1) is connected to only one side, so it can only contribute \(+1\) times (or \(-1\) times) its elevation.

Therefore, rather than placing bridges in scattered segments to create multiple short paths, it is most efficient to consolidate all bridges into one large path (length \(K\), with \(K+1\) vertices), leaving the remaining \(N - (K+1)\) vertices as isolated points (no bridges connected).

2. Contribution (Coefficients) of Each Element in the Path

In a path of length \(K\), the sum of elevation differences can be maximized by arranging the elements in a zigzag pattern (alternating between local maxima and minima). We analyze how each element of the sorted elevation array \(A\) contributes to the total (its coefficient). For maximization, negative coefficients are assigned to smaller values, and positive coefficients are assigned to larger values.

• When \(K\) is odd: The number of vertices is even (\(K+1\)).

  • Negative side: The smallest \(\frac{K-1}{2}\) elements get coefficient \(-2\), the next \(1\) element gets coefficient \(-1\).
  • Positive side: The largest \(\frac{K-1}{2}\) elements get coefficient \(+2\), the next \(1\) element gets coefficient \(+1\).
  • Concrete example: When \(K=3\) (4 vertices) Let the ordering be \(x_1 < x_2 < x_3 < x_4\). An optimal arrangement is \(x_2, x_4, x_1, x_3\), etc., giving sum of differences = \((x_4 - x_2) + (x_4 - x_1) + (x_3 - x_1) = 2x_4 + x_3 - 2x_1 - x_2\). The coefficients in ascending order are \(-2, -1, +1, +2\), which matches the rule above.

• When \(K\) is even: The number of vertices is odd (\(K+1\)). In this case, we choose the pattern that yields the larger value from the following two:

  • Pattern 1 (one more peak):
    • Negative side: The smallest \(\frac{K}{2}-1\) elements get \(-2\), the next \(2\) elements get \(-1\).
    • Positive side: The largest \(\frac{K}{2}\) elements get \(+2\).
  • Pattern 2 (one more valley):
    • Negative side: The smallest \(\frac{K}{2}\) elements get \(-2\).
    • Positive side: The largest \(\frac{K}{2}-1\) elements get \(+2\), the next \(2\) elements get \(+1\).

3. Speedup Using Prefix Sums

By sorting the elevations \(A\) in ascending order and preparing a prefix sum array \(S\) (\(S[i] = \sum_{j=0}^{i-1} A[j]\)), we can compute the weighted sum with these coefficients in \(O(1)\).

• Left side (negative contribution) calculation: Multiplying the smallest \(a\) elements by \(-2\) and the remaining needed elements (to make a total of \(K-a\)) by \(-1\) can be expressed as: $\(\text{get\_L}(a) = -S[a] - S[K-a]\)$
• Right side (positive contribution) calculation: Multiplying the largest \(c\) elements by \(+2\) and the remaining needed elements (to make a total of \(K-c\)) by \(+1\) can be expressed as: $\(\text{get\_R}(c) = 2S[N] - S[N-c] - S[N-K+c]\)$

Algorithm

1. Sort the elevation array \(A\) in ascending order.
2. Build the prefix sum array \(S\).
3. Based on the parity of \(K\), determine the optimal \(a\) (number of elements multiplied by \(-2\) on the left side) and \(c\) (number of elements multiplied by \(+2\) on the right side).
   • When \(K\) is odd: Set \(a = (K-1)/2\), \(c = (K-1)/2\), and compute \(\text{get\_L}(a) + \text{get\_R}(c)\).
   • When \(K\) is even: Choose the larger value between:
     • Pattern 1: \(a = K/2 - 1\), \(c = K/2\)
     • Pattern 2: \(a = K/2\), \(c = K/2 - 1\)
4. Output the computed maximum value.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the array \(A\) takes \(O(N \log N)\). Building the prefix sum is \(O(N)\), and computing the answer is \(O(1)\), so the overall bottleneck is the sort. This runs sufficiently fast for the constraint \(N \leq 10^6\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the array \(A\) and the prefix sum array \(S\).

Implementation Notes

• Overflow caution: Since elevations \(A_i\) can be up to \(10^9\) and their total sum can reach \(10^{15}\), computations must use long long type (64-bit integers).

• Prefix sum boundaries: Using a 1-indexed prefix sum array \(S\) reduces the risk of out-of-bounds access and allows concise range sum calculations.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // 標高を昇順にソート
    sort(A.begin(), A.end());

    // 累積和の計算
    vector<long long> S(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        S[i + 1] = S[i] + A[i];
    }

    // 左側の寄与の計算
    auto get_L = [&](int a) {
        return -S[a] - S[K - a];
    };

    // 右側の寄与の計算
    auto get_R = [&](int c) {
        return 2 * S[N] - S[N - c] - S[N - K + c];
    };

    long long ans = 0;
    if (K % 2 == 1) {
        int a = (K - 1) / 2;
        int c = (K - 1) / 2;
        ans = get_L(a) + get_R(c);
    } else {
        int a1 = K / 2, c1 = K / 2 - 1;
        int a2 = K / 2 - 1, c2 = K / 2;
        ans = max(get_L(a1) + get_R(c1), get_L(a2) + get_R(c2));
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.