AtCoder ABC #149 : E - Handshake

Eは簡単目でした。
https://atcoder.jp/contests/abc149/tasks/abc149_e

問題

N要素の整数列A[i]が与えられる。
要素の対(x,y)を選ぶ。この時x=yでもよいし、xとyが逆順になったものは別の対とみなす。
そのような対をM個選び、A[x]+A[y]の総和を最大化せよ。

解法

当然大きな順にM個選ぶので、選ぶ対の下限Dを二分探索し、D以上の和がM組以上となるようにしよう。
Aを昇順にしておけば、各xに対しyの候補はA[y]≧D-A[x]となる個数なのでx毎にO(NlogN)で求められる。
あとはD以上となる要素対の総和を求めよう。
D以上となる要素対がM個を超える場合もあるので最後はそこを調整する。

int N;
ll M;
ll A[101010],S[202020];

ll num(ll v) {
	ll tot=0;
	int i;
	FOR(i,N) {
		tot+=N-(lower_bound(A,A+N,v-A[i])-A);
	}
	return tot;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i];
	}
	sort(A,A+N);
	FOR(i,N) S[i+1]=S[i]+A[N-1-i];
	
	ll mi=0;
	for(i=40;i>=0;i--) if(num(mi+(1LL<<i))>=M) mi+=1LL<<i;
	
	ll num=0;
	ll ret=0;
	FOR(i,N) {
		x=N-(lower_bound(A,A+N,mi-A[i])-A);
		num+=x;
		ret+=A[i]*x+S[x];
		
	}
	ret-=(num-M)*mi;
	cout<<ret<<endl;
}

まとめ

普段使うPCじゃないとやっぱりやりにくい。