PKU 2549 Sumsets
http://poj.org/problem?id=2549
n個の異なる数字が与えられる。
その中から異なる4つの数字を取り出してa+b+c=dとなるようなもののうち最大のdを求めろというような問題。
半分全列挙使いました。
最初map
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(); }