해결 접근법

첫 번째 방법:

i번 가게를 선택하는 경우, 명백하게 a 값이 가장 큰 i-1개 가게는 반드시 선택해야 합니다. 따라서 마지막 가게 선택 방식만 고려하면 됩니다. a 값이 i번째로 큰 가게를 선택하는 방법과, 남은 가게 중 s 값이 가장 큰 가게를 선택하는 방법 중에서 선택해야 합니다.

각 가게의 정보(s와 a)를 구조체에 저장한 후, a 값을 기준으로 내림차순으로 정렬합니다. 그런 다음 sum 배열을 사용하여 a 값의 누적 합을 계산하고, maxs[i]는 i개 가게 중 최대 s 값을, maxa[i]는 i번째부터 n번째 가게 중 하나를 선택했을 때의 최대 가치(2*s + a)를 나타냅니다.

요구되는 각 i에 대해, 정답 ans[i]는 다음 두 값 중 최대값이 됩니다:

• a 값이 가장 큰 i개 가게를 선택한 경우
• a 값이 가장 큰 i-1개 가게와, 나머지 가게 중 가장 큰 기여를 하는 가게 하나를 선택한 경우

수식으로 표현하면 다음과 같습니다: ans[i] = max(sum[i] + 2*maxs[i], sum[i-1] + maxa[i])

두 번째 방법:

ans 값은 i가 증가함에 따라 단조 증가하므로, 이전 정답에 특정 값을 추가하여 계산할 수 있습니다. 매 선택에서 두 가지 경우로 나눌 수 있습니다. 현재까지 선택한 가게 중 가장 멀리 있는 가게의 주소를 now라고 가정하면:

• now보다 작은 주소 중 a 값이 가장 큰 가게 k를 선택했을 때의 기여도: a[k]
• now보다 큰 주소 중 기여도(2*(s[k]-now) + a[k])가 가장 큰 가게 k를 선택했을 때의 기여도

따라서 두 경우 중 최대값을 선택하면 됩니다.

이 방법을 구현하기 위해 두 개의 우선순위 큐(최대 힙)를 사용하는 것이 편리합니다. q1에는 now 왼쪽에 있는 가게들을, q2에는 now 오른쪽에 있는 가게들을 저장합니다.

오른쪽 가게를 업데이트할 때, q2에서 하나를 꺼낸 후, now와 q2.top() 사이의 모든 가게들을 q1에 추가합니다. 그런 다음 now 값을 업데이트합니다. 왼쪽 가게를 업데이트할 때, q1에서 하나를 꺼내고 q2는 그대로 둡니다.

이렇게 하면 q2에서 가게를 선택할 때마다, 주소가 now보다 작은 모든 가게들을 먼저 제거해야 합니다.

AC 코드

첫 번째 방법

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 100005;
int n, prefixSum[MAXN], maxS[MAXN], maxA[MAXN];
struct Shop {
    int location, value;
    bool operator <(const Shop &other) const {
        return value > other.value;
    };
} shops[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> shops[i].location;
    }
    for (int i = 1; i <= n; i++) {
        cin >> shops[i].value;
    }
    
    sort(shops + 1, shops + n + 1);
    
    for (int i = 1; i <= n; i++) {
        prefixSum[i] = prefixSum[i-1] + shops[i].value;
        maxS[i] = max(maxS[i-1], shops[i].location);
    }
    
    for (int i = n; i >= 1; i--) {
        maxA[i] = max(maxA[i+1], 2 * shops[i].location + shops[i].value);
    }
    
    for (int i = 1; i <= n; i++) {
        cout << max(prefixSum[i] + 2 * maxS[i], prefixSum[i-1] + maxA[i]) << '\n';
    }
    
    return 0;
}

두 번째 방법

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 100005;
int n;
long long totalAnswer;
struct Shop {
    int location, value;
    bool operator <(const Shop &other) const {
        return 2 * location + value < 2 * other.location + other.value;
    };
} stores[MAXN];

priority_queue<int> leftHeap;
priority_queue<Shop> rightHeap;

void printAnswer() {
    cout << totalAnswer << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> stores[i].location;
    }
    for (int i = 1; i <= n; i++) {
        cin >> stores[i].value;
    }
    
    for (int i = 1; i <= n; i++) {
        rightHeap.push(stores[i]);
    }
    
    int currentLocation = 0;
    for (int i = 1; i <= n; i++) {
        Shop currentShop;
        if (!rightHeap.empty()) {
            currentShop = rightHeap.top();
            while (currentShop.location < currentLocation && !rightHeap.empty()) {
                rightHeap.pop();
                if (!rightHeap.empty()) currentShop = rightHeap.top();
            }
        }
        
        if (leftHeap.empty()) {
            if (!rightHeap.empty()) {
                currentShop = rightHeap.top();
                rightHeap.pop();
                currentLocation = currentShop.location;
                totalAnswer += currentShop.value + 2 * currentShop.location - 2 * currentLocation;
                printAnswer();
            }
            continue;
        }
        
        if (rightHeap.empty()) {
            int leftValue = leftHeap.top();
            leftHeap.pop();
            totalAnswer += leftValue;
            printAnswer();
            continue;
        }
        
        int leftValue = leftHeap.top();
        int rightValue = currentShop.value + 2 * currentShop.location - 2 * currentLocation;
        
        if (leftValue > rightValue) {
            leftHeap.pop();
            totalAnswer += leftValue;
        } else {
            rightHeap.pop();
            currentLocation = currentShop.location;
            totalAnswer += rightValue;
        }
        printAnswer();
    }
    
    return 0;
}

// NOIP2015 초등부 t4