PKU 2549 Sumsets

http://poj.org/problem?id=2549
n個の異なる数字が与えられる。
その中から異なる4つの数字を取り出してa+b+c=dとなるようなもののうち最大のdを求めろというような問題。

半分全列挙使いました。
最初map >を使ったらTLEしたので、ハッシュを使ったのですが、そうしたら今度はWAしたので、よく問題を見ると、最大のdというのを見落としていました。

int n;
ll arr[1000];

typedef struct _node{
  ll key;
  PI val[10];
  int sz;
  _node*next;
}node;

const int hashMod=1226803;
node ent[600000];
int sz=0;
node*hash[hashMod];

void insert(ll key,PI val){
  int ha=(key%hashMod+hashMod)%hashMod;
  for(node*p=hash[ha];p;p=p->next){
    if(p->key==key){
      if(p->sz<10)
        p->val[p->sz++]=val;
      return;
    }
  }
  node *p=hash[ha];
  hash[ha]=ent+sz++;
  hash[ha]->key=key;
  hash[ha]->val[0]=val;
  hash[ha]->sz=1;
  hash[ha]->next=p;
}

pair<PI*,int> get(ll key){
  int ha=(key%hashMod+hashMod)%hashMod;
  for(node*p=hash[ha];p;p=p->next){
    if(p->key==key)
      return mp(p->val,p->sz);
  }
  return mp((PI*)(NULL),0);
}

void solve(){
  memset(hash,0,sizeof(hash));
  sz=0;
  rep(i,n){
    scanf("%lld",arr+i);
    rep(j,i)insert(arr[j]+arr[i],mp(i,j));
  }
  bool ok=false;
  ll ans=-(1LL<<40);
  rep(i,n){
    rep(j,n){
      if(i==j)continue;
      ll di=arr[j]-arr[i];
      pair<PI*,int> se=get(di);
      if(!se.S)continue;
      for(int k=0;k<se.S;++k){
        PI* it=se.F+k;
        if(it->F!=i && it->F!=j &&
           it->S!=i && it->S!=j){
          ans=max(arr[j],ans);
          ok=true;
        }
      }
    }
  }
  if(ok)cout<<ans<<endl;
  else cout<<"no solution"<<endl;
}

main(){
  while(cin>>n,n)solve();
}