Submission #53368651

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define REP_(i, a_, b_, a, b, ...) \
  for (int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(v) v.begin(), v.end()

int main() {
  int N;
  cin >> N;
  vector<ll> A(N);
  ll lim = 100000000;
  vector<ll> acc(N + 1);
  acc[0] = 0;
  REP(i, N) { cin >> A[i]; }

  sort(A.begin(), A.end());
  REP(i, N) {
    // cout << A[i] << " ";
    acc[i + 1] = acc[i] + A[i];
    // acc[i + 1] %= lim;
  }
  // cout << endl;
  // cout << endl;

  ll ans = 0;
  REP(i, N - 1) {
    // cout << A[i] << endl;
    // cout << "A[i]について二分探索する" << A[i] << endl;
    ll v = lim - A[i];
    auto it = lower_bound(A.begin() + i + 1, A.end(), v);
    if (it != A.end()) {
      // 二分探索にヒットしたので10**8を引く回数を求める
      int idx = it - A.begin();
      // cout << "合計が10**8以上になる最初の数: " << idx << " " << *it << endl;
      // cout << "i+1から終端までの合計" << acc[N] - acc[i + 1] << endl;
      ans += acc[N] - acc[i + 1];
      ans += A[i] * (N - i - 1);
      // cout << N - idx << "回 10**8を減産する" << endl;
      ans -= lim * (N - idx);
    } else {
      ans += acc[N] - acc[i + 1];
      ans += A[i] * (N - i - 1);
    }
    // cout << ans << endl;
  }
  cout << ans << endl;
}

Submission Info

Judge Result