Overview

This problem asks you to arrange observation spots in any order you like, choose exactly \(K\) adjacent pairs, and maximize the sum of absolute differences in elevation.

The conclusion is that by sorting the elevations and considering an arrangement that alternates between “low elevations” and “high elevations,” we can find the maximum value.

Analysis

First, let’s focus only on the selected suspension bridges.

The thrill value of a suspension bridge connecting two points with elevations \(x < y\) is

\(y - x\)

In other words, this bridge can be thought of as assigning coefficients:

• \(+1\) to the higher point
• \(-1\) to the lower point

Also, a single observation spot is adjacent to at most 2 suspension bridges (on its left and right in the arrangement).
Therefore, any elevation is counted with \(+1\) or \(-1\) at most 2 times.

To maximize, we want:

• \(+\) coefficients assigned to elevations as large as possible
• \(-\) coefficients assigned to elevations as small as possible

For this reason, the elevations we should use are concentrated on the “small side” and “large side” after sorting.

Additionally, if we split the bridges into multiple disconnected paths, the number of endpoints increases.
Endpoints can only have a coefficient with absolute value \(1\), but interior points can have a coefficient with absolute value \(2\).

Therefore, the maximum is achieved by using all \(K\) bridges as a single path, and arranging elevations as:

low, high, low, high, …

in an alternating fashion.

The remaining unused observation spots can simply be placed outside this sequence.

---

Let the sorted array be 0-indexed:

\(A_0 \leq A_1 \leq \cdots \leq A_{N-1}\)

Also define:

• \(S(t)\): sum of the smallest \(t\) elements
• \(L(t)\): sum of the largest \(t\) elements

When \(K\) is odd

Let \(K = 2m - 1\).

The number of vertices used is \(K+1 = 2m\).

When arranged alternately:

• \(m\) elements from the high side are used
• \(m\) elements from the low side are used

Interior points have coefficient \(\pm 2\), and endpoints have coefficient \(\pm 1\).

On the high side, the smallest one becomes an endpoint with \(+1\), and the rest get \(+2\).
On the low side, the largest one becomes an endpoint with \(-1\), and the rest get \(-2\).

Therefore, the answer is

\(2(L(m) - S(m)) - (A_{N-m} - A_{m-1})\)

For example, if \(K=3\) and elevations are \(1,2,99,100\):

\(2((99+100)-(1+2)) - (99-2) = 295\)

And indeed, arranging as

\(2,100,1,99\)

gives

\(|2-100| + |100-1| + |1-99| = 98+99+98=295\)

When \(K\) is even

Let \(K = 2m\).

The number of vertices used is \(K+1 = 2m+1\).

When arranged alternately, both endpoints are either:

• On the high side
• On the low side

When endpoints are on the high side

We use \(m+1\) elements from the high side and \(m\) elements from the low side.

• All \(m\) elements on the low side are interior, so coefficient \(-2\)
• Of the \(m+1\) elements on the high side, 2 endpoints have coefficient \(+1\)
• The remaining \(m-1\) have coefficient \(+2\)

Therefore, the candidate value is

\(-2S(m) + A_{N-m-1} + A_{N-m} + 2L(m-1)\)

When endpoints are on the low side

We use \(m+1\) elements from the low side and \(m\) elements from the high side.

• All \(m\) elements on the high side are interior, so coefficient \(+2\)
• Of the \(m+1\) elements on the low side, 2 endpoints have coefficient \(-1\)
• The remaining \(m-1\) have coefficient \(-2\)

Therefore, the candidate value is

\(2L(m) - \left(2S(m-1) + A_{m-1} + A_m\right)\)

The larger of these two is the answer.

Algorithm

1. Sort the elevation array \(A\) in ascending order.
2. Create a prefix sum array pref.
3. Define the following:
   • sum_small(t) = sum of the smallest \(t\) elements
   • sum_large(t) = sum of the largest \(t\) elements
4. Handle cases based on the parity of \(K\):
   • If \(K\) is odd, compute the answer using the formula for the odd case.
   • If \(K\) is even, compute both cases (endpoints on high side and endpoints on low side) and take the larger one as the answer.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting is the dominant factor.
• Space complexity: \(O(N)\)
  • For storing the array and prefix sums.

Implementation Notes

• The answer can be at most approximately \(10^6 \times 10^9 = 10^{15}\), so use long long.

• In the even case, when \(m=1\), sum_small(m-1) and L(m-1) become sums of 0 elements. Using prefix sums handles this naturally.

• Using 0-indexed notation makes it easier to correspond with the formulas in the code.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<long long> A(N);
    for (auto &x : A) cin >> x;

    sort(A.begin(), A.end());

    vector<long long> pref(N + 1, 0);
    for (int i = 0; i < N; i++) pref[i + 1] = pref[i] + A[i];

    auto sum_small = [&](int t) -> long long {
        return pref[t];
    };

    auto sum_large = [&](int t) -> long long {
        return pref[N] - pref[N - t];
    };

    long long ans;

    if (K % 2 == 1) {
        int m = (K + 1) / 2;
        ans = 2 * (sum_large(m) - sum_small(m)) - (A[N - m] - A[m - 1]);
    } else {
        int m = K / 2;

        long long ans1 = -2 * sum_small(m)
                       + A[N - m - 1] + A[N - m]
                       + 2 * (pref[N] - pref[N - m + 1]);

        long long ans2 = 2 * sum_large(m)
                       - (2 * sum_small(m - 1) + A[m - 1] + A[m]);

        ans = max(ans1, ans2);
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.