This document outlines a greedy strategy for a sales optimization problem.

Let's consider the sample input:

6
1 2 3 4 5 6
4 2 3 5 3 1

Assume the current location is at point X = 1. We define an array F, where F[i] represents the additional contribtuion to the total answer by visiting user a[i] without any detours. ans will store the cumulative answer, and now will track furthest point reached.

For X = 1, F[i] = s[i] * 2 + a[i]. The calculated F array is {6, 6, 9, 13, 13, 13}. The algroithm selects the maximum value from F, which is 13. Let now be the index of this maximum value, so now = 4 (indices 5 or 6 are also valid choices). The answer is updated: ans += F[4], resulting in ans = 13.

Now, let's analyze the impact of this choice on other potential F[i] values when considering X = 2.

If s[i] < s[now] (i.e., user i is to the left of now), then F[i] becomes a[i]. This is because user i can be visited on the way to now. The reasoning here is that the travel fatigue for visiting user i first or visiting now first is equivalent. The F array transforms to {4, 2, 3, /, 13, 13} (index 4 is now marked as unavailable).

If s[i] > s[now] (i.e., user i is to the right of now), then F[i] = (s[i] - s[now]) * 2 + a[i]. This accounts for the extra travel distance to i and back, which is 2 * (s[i] - s[now]) added to the base visit cost a[i]. The F array becomes {4, 2, 3, /, 5, 5}.

We then find the maximum value in the updated F array. Let now be updated to index 6 (index 5 is also possible). ans += F[6], so ans = 18. The F array is updated again: {4, 2, 3, /, 3, /}. F[5] is now 3 because it's to the left of the new now (index 6).

Moving to X = 3: ans += F[1], ans = 22. F becomes {/, 2, 3, /, 3, /}.

For X = 4: ans += F[3], ans = 25. F becomes {/, 2, /, /, 3, /}.

For X = 5: ans += F[5], ans = 28. F becomes {/, 2, /, /, /, /}.

For X = 6: ans += F[2], ans = 30. F becomes {/, /, /, /, /, /}.

The final sequence of answers is:

13
18
22
25
28
30

To efficiently find the maximum value at each step, we can use auxiliary data structures. maxn[now] can store the maximum F[i] for i > now. This helps manage values to the right of the current position.

For values to the left of now, which require deletion of the maximum, a priority_queue is suitable. It can maintain the maximum a[i] values efficiently.

Notice that the F array itself doesn't need to be explicitly constructed or modified. The logic for updating a[i] for points to the left of now is handled by the priority queue. For points to the right, maxn[now] can be updated by subtracting s[now] * 2. The value maxn[now] = s[i] * 2 + a[i] (where i is the current maximum index) adjusted by -s[now] * 2 effectively calculates a[i] + (s[i] - s[now]) * 2, which corresponds to the F[i] calculation for points to the right.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#nclude <algorithm>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int> s(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> s[i];
    }

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    std::vector<std::pair<int, long long>> max_suffix(n + 2);
    max_suffix[n + 1] = {0, -2e9 - 7}; // Initialize with a very small value

    for (int i = n; i >= 1; --i) {
        max_suffix[i] = max_suffix[i + 1];
        long long current_val = (long long)s[i] * 2 + a[i];
        if (current_val >= max_suffix[i].second) {
            max_suffix[i] = {i, current_val};
        }
    }

    long long total_ans = 0;
    int current_pos = 1;
    std::priority_queue<int> left_customers;

    for (int count = 0; count < n; ++count) {
        int left_max_potential = (left_customers.empty() ? -2e9 - 7 : left_customers.top());
        int right_max_potential = (current_pos == n) ? -2e9 - 7 : (max_suffix[current_pos + 1].second - (long long)s[current_pos] * 2);

        if (left_max_potential >= right_max_potential) {
            total_ans += left_max_potential;
            left_customers.pop();
        } else {
            total_ans += right_max_potential;
            int next_best_idx = max_suffix[current_pos + 1].first;
            for (int i = current_pos + 1; i < next_best_idx; ++i) {
                left_customers.push(a[i]);
            }
            current_pos = next_best_idx;
        }
        std::cout << total_ans << std::endl;
    }

    return 0;
}