\(f(x,y)\) を扱いやすい形に言い換えましょう。今回の制約の範囲では、\(f(x,y)\) は \(x+y < 10^8\) のとき \(x+y\)、\(x+y\geq 10^8\) のとき \(x+y-10^8\) に等しいことがわかります。

このことから、\(\sum_{i=1}^{N-1}\sum_{j=i+1}^N A_i + A_j\) を求め、そこから \(A_i + A_j\) が \(10^8\) 以上となる整数組 \((i,j)\ (1\leq i <j\leq N)\) の個数 \(\times 10^8\) を引けば答えが求まります。

\(\sum_{i=1}^{N-1}\sum_{j=i+1}^N A_i + A_j\) を考えると、各項が \(N-1\) 回加算されることから、これは \((N-1)\sum_{i=1}^{N} A_i\) と言い換えられ、\(\mathrm{O}(N)\) で求められます。

次に、\(A_i + A_j\) が \(10^8\) 以上となる整数組 \((i,j)\ (1\leq i <j\leq N)\) の個数を求めましょう。

\(A\) を昇順に並び替えても答えは変わらないので昇順に並び替えておきます。すると、\(A_i + A_j\geq 10^8\) なる \(j\) の最小値は、\(i\) が増加するにつれて単調に減少することがわかります。以上から、尺取り法を用いることで条件を満たす整数組の個数を求められます。 \(A_i = 5\times 10^7\) の場合に余計に数えすぎないよう注意してください。

実装例(C++):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(auto &v : a) cin >> v;
  sort(a.begin(), a.end());
  int r = n;
  ll cnt = 0, res = 0;
  for(int i = 0; i < n; i++) {
    r = max(r, i + 1);
    while(r - 1 > i and a[r - 1] + a[i] >= 100000000) {
      r--;
    }
    cnt += n - r;
  }
  for(int i = 0; i < n; i++) res += ll(a[i]) * (n - 1);
  res -= cnt * 100000000;
  cout << res << endl;
}