POJ.2549 Sumsets

1.Problem
http://poj.org/problem?id=2549

2.Idea
Semi-enumeration

3.Source

 #define MAX_N 1000  
 int n;  
 ll a[1003];  
 struct Item {  
      ll v;  
      int s, t;  
      bool operator < (const Item &a)const {  
           return v < a.v;  
      }  
 } ab[MAX_N * MAX_N], cd[MAX_N * MAX_N];  
 void solve()  
 {  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j < n; j++) {  
                ab[i*n + j].v = a[i] + a[j];  
                ab[i*n + j].s = i;  
                ab[i*n + j].t = j;  
                cd[i*n + j].v = a[i] - a[j];  
                cd[i*n + j].s = i;  
                cd[i*n + j].t = j;  
           }  
      }  
      ll ans = -1LL << 40;  
      sort(ab, ab + n*n);  
      for (int i = 0; i < n*n; i++) {  
           int j = lower_bound(ab, ab + n*n, cd[i]) - ab;  
           while (j < n*n && ab[j].v == cd[i].v) {  
                if (ab[j].s != ab[j].t &&  
                     cd[i].s != cd[i].t &&  
                     ab[j].s != cd[i].s &&  
                     ab[j].s != cd[i].t &&  
                     ab[j].t != cd[i].s &&  
                     ab[j].t != cd[i].t) {  
                     ans = max(ans, a[cd[i].s]);  
                }  
                j++;  
           }  
      }  
      if (ans == -1LL << 40) cout << "no solution" << endl;  
      else cout << ans << endl;  
 }  
 int main()  
 {  
      while (cin >> n) {  
           if (n == 0) break;  
           for (int i = 0; i < n; i++) cin >> a[i];  
           solve();  
      }  
      return 0;  
 }