\(P_N = i\)、すなわち巨人 \(i\) が一番上にいるときの一番上に立っている巨人の頭の高さは \(B_i + \sum_{j \neq i}A_j\) です。

\(B_i + \sum_{j \neq i}A_j = B_i - A_i + \sum_{j = 1}^{N} A_j\) であり、答えは \(i = 1,2, \ldots, N\) におけるこの値の最大値ですが、\(\sum_{j = 1}^{N} A_j\) の値は \(i\) に依らないことを利用すると \(\max (B_i - A_i)\) の値を求めればよいことがわかります。

これは for ループなどを利用することで時間計算量 \(O(N)\) で計算可能です。

実装例

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

int main() {
	int n;
	cin >> n;
	vector<ll> a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
	ll m = 0;
	for (int i = 0; i < n; i++) m = max(m, b[i] - a[i]);
	ll ans = m;
	for (int i = 0; i < n; i++) ans += a[i];
	cout << ans << '\n';
}