不错的贪心题。
我们考虑一对照片只有一张的情况。那么先后手会按照 \(a + b\) 降序取。因为若 \(a_i + b_i \ge a_j + b_j\)，变形得 \(a_i - b_j \ge a_j - b_i\) 且 \(b_i - a_j \ge b_j - a_i\)，所以对于双方先取 \(i\) 一定是不劣的。
回到原题，如果 \(a_{i, 1} + b_{i, 1} \ge a_{i, 2} + b_{i, 2}\)，那么 \((a_{i, 1}, b_{i, 1})\) 和 \((a_{i, 2}, b_{i, 2})\) 会成为先后手争夺的目标，因为双方都想取走上面的。我们把这种物品单独处理，也就是按照 \(a + b\) 降序排序，然后先后手交替取。
取完这种物品后，就还剩下 \(a_{i, 1} + b_{i, 1} < a_{i, 2} + b_{i, 2}\) 的物品，变形得 \((a_{i, 1} - b_{i, 2}) + (b_{i, 1} - a_{i, 2}) < 0\)。分类讨论是哪一项 \(< 0\)：
- 如果 \(a_{i, 1} - b_{i, 2} < 0\) 且 \(b_{i, 1} - a_{i, 2} < 0\)，那么这个物品就废掉了，因为双方都不想先取上面的物品，否则会给另一方带来收益。
- 如果 \(a_{i, 1} - b_{i, 2} < 0\) 且 \(b_{i, 1} - a_{i, 2} \ge 0\)，那么 A 肯定不会取 \(a_{i, 1}\)，但是 B 取 \(b_{i, 1}\) 一定不劣。这种情况我们把 \(a_{i, 2} - b_{i, 1}\) 累加进答案。
- 否则 \(a_{i, 1} - b_{i, 2} \ge 0\) 且 \(b_{i, 1} - a_{i, 2} < 0\)，这种情况跟上面是对称的，B 肯定不会取 \(b_{i, 1}\)，但是 A 取 \(a_{i, 1}\) 一定不劣，把 \(a_{i, 1} - b_{i, 2}\) 累加进答案。
code
// Problem: F. Family Photos
// Contest: Codeforces - Canada Cup 2016
// URL: https://codeforces.com/problemset/problem/725/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
void solve() {
int n;
scanf("%d", &n);
vector<pii> vc;
ll ans = 0;
while (n--) {
int a1, b1, a2, b2;
scanf("%d%d%d%d", &a1, &b1, &a2, &b2);
if (a1 + b1 >= a2 + b2) {
vc.pb(a1, b1);
vc.pb(a2, b2);
} else if (b1 >= a2) {
ans += a2 - b1;
} else if (a1 >= b2) {
ans += a1 - b2;
}
}
sort(vc.begin(), vc.end(), [&](pii a, pii b) {
return a.fst + a.scd > b.fst + b.scd;
});
for (int i = 0; i < (int)vc.size(); ++i) {
ans += ((i & 1) ? -vc[i].scd : vc[i].fst);
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}