PKU 3663 Costume Party

http://poj.org/problem?id=3663
長さn<=20000の数列が与えられる。この時この要素の中から2組取ってきて、その和がs以下になるような組み合わせはいくつあるか、というような問題。

ソートして2分探索。O(nlogn)

int in[20000];

main(){
  int n,s;
  cin>>n>>s;
  rep(i,n)cin>>in[i];

  sort(in,in+n);
  int ans=0;
  rep(i,n-1){
    if(in[i]+in[i+1]>s)break;
    ans+=upper_bound(in+i+1,in+n,s-in[i])-in-i-1;
  }
  cout<<ans<<endl;
}