526互联

abc062d <优先队列>

发布时间 2023-07-08 17:38:23作者: O2iginal

D - 3N Numbers
参考

// https://atcoder.jp/contests/abc062/tasks/arc074_b
// 优先队列 
// maxs[i] 为前i个数中, 选择n个数的最大和
// mins[i] 为i+1~3n 的数中, 选择n个数的最大和
// 使用优先队列维护最大/最小的n个数
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10, INF = 2e9;
LL a[N], maxs[N], mins[N];

void solv()
{
    int n;
    cin >> n;
    priority_queue<LL> minq;
    priority_queue<LL, vector<LL>, greater<LL>> maxq;
    for (int i = 1; i <= n * 3; i++) cin >> a[i];
    for (int i = 1; i <= n * 2; i++)
    {
        if (i <= n)
        {
            maxs[i] = maxs[i - 1] + a[i];
            maxq.push(a[i]);
        }
        else
        {
            if (maxq.top() < a[i])
            {
                maxs[i] = maxs[i - 1] + a[i] - maxq.top();
                maxq.pop();
                maxq.push(a[i]);
            }
            else
                maxs[i] = maxs[i - 1];
        }
    }
    for (int i = n * 3; i > n; i--)
    {
        if (i > n * 2)
        {
            mins[i] = mins[i + 1] + a[i];
            minq.push(a[i]);
        }
        else
        {
            if (minq.top() > a[i])
            {
                mins[i] = mins[i + 1] + a[i] - minq.top();
                minq.pop();
                minq.push(a[i]);
            }
            else
                mins[i] = mins[i + 1];
        }
    }
    LL ans = -1e15;
    for (int i = n; i <= 2 * n; i++)
    {
        ans = max(ans, maxs[i] - mins[i + 1]);
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solv();
    }
    return 0;
}