ABC062-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'の前半と後半の和は独立に考えることが出来るところがポイントなのかなぁ。