ABC062-D 3N Numbers

D - 3N Numbers

• 考察

• code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define show(x) cout<<#x<<"="<<x<<"\n"
using namespace std;

int n;
int a[3*100001];
ll lmax[100002];
ll rmin[100002];
const ll inf=(ll)1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout<<fixed;
#ifdef LOCAL_DEFINE
    FILE *stream1;
    //FILE *stream2;
    stream1=freopen("in","r",stdin);
    //stream2=freopen("out","w",stdout);
    if(stream1==NULL)return 0;
    //if(stream2==NULL)return 0;
#endif
    cin>>n;
    ll suml=0,sumr=0;
    for(int i=0;i<3*n;i++){
        cin>>a[i];
        if(i<n)suml+=a[i];
    }
    priority_queue<int> l;
    for(int i=0;i<n;i++){
        l.push(-a[i]);
    }
    lmax[0]=suml;
    for(int i=0;i<n;i++){
        l.push(-a[n+i]);
        suml+=a[n+i]+l.top();
        l.pop();
        lmax[i+1]=suml;
    }
    priority_queue<int> r;
    for(int i=0;i<n;i++){
        r.push(a[2*n+i]);
        sumr+=a[2*n+i];
    }
    rmin[n]=sumr;
    for(int i=0;i<n;i++){
        r.push(a[2*n-1-i]);
        sumr+=a[2*n-1-i]-r.top();
        r.pop();
        rmin[n-1-i]=sumr;
    }
    ll ans=-inf;
    for(int i=0;i<=n;i++){
        //cerr<<lmax[i]<<" "<<rmin[i]<<endl;
        ans=max(ans,lmax[i]-rmin[i]);
    }
    cout<<ans<<endl;
#ifdef LOCAL_DEFINE
    cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
    fclose(stream1);
    //fclose(stream2);
#endif
    return 0;
}

• 感想

最近になってやっと問題はしっかり考察しようと思うようになった。
紙に書くことは大切だね。
今回はa'の前半と後半の和は独立に考えることが出来るところがポイントなのかなぁ。