ARC 074 D問題 3N Numbers

解説

この問題はどこで前半と後半の区切りになるのかを考えます。 例えば | が前後半の区切りだとすると

a, b, c d, e | f, g, h, i

この棒をずらしていくのですがn~2*nの間しか動くことができません。

• 先頭からN個数字をとる場合
  a, b, c, d, e, f | g, h, i

• 後ろからN個数字をとる場合
  a, b, c | d, e, f, g, h, i

このように極端な例を考えてみると | が動ける位置がわかるので その|の位置を一つづつずらして前半から大きい順にN個の和と後半から小さい順にN個の和を別々に計算し最後に最大になるa'の値を出力すれば正解です。

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

int main(void){
    int n, a[300005];
    long long sum_front=0, sum_back=0;
    
    vector<ll> sf, sb;
    priority_queue<ll, vector<ll>, greater<ll> > que_front;
    priority_queue<ll> que_back;
    
    cin >> n;

    for( int i = 0; i< 3 * n; i++ ){
        cin >> a[i];
        if(i < n){
            sum_front += a[i];
            que_front.push(a[i]);
        }else if( 2*n <= i ){
            sum_back += a[i];
            que_back.push(a[i]);
        }
    }

    sf.push_back(sum_front);
    sb.push_back(sum_back);
    
    for( int i = 0; i < n ; i++ ){
        que_front.push(a[i+n]);
        sum_front += a[i+n];
        sum_front -= que_front.top();
        que_front.pop();
        sf.push_back(sum_front);

        que_back.push(a[2*n-1-i]);
        sum_back += a[2*n-1-i];
        sum_back -= que_back.top();
        que_back.pop();
        sb.push_back(sum_back);
    }
    reverse(sb.begin(), sb.end());
    long long ans = sf[0] - sb[0];
    for( int i = 1; i <= n; i++ ){
        ans = max(ans, sf[i] - sb[i]);
    }
    cout << ans << endl;
    return 0;
}