13135번: Corrupt Election

https://www.acmicpc.net/problem/13135


$O(n^2)$

(ai,bi)를 (max(ai,bi),ai+bi) 로 바꾼 다음 생각해보자.
제외되지 않는 점들은 x<X이고 y<Y를 만족한다. 해당 점들이 조건을 만족하는지 보고 가능한 X, Y 경우의 수를 구하자.
정렬을 이용한다면 O(n2)에 구할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, x[1001];
pair<int, int> p[1001];
long long r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].first, &p[i].second), x[i] = max(p[i].first, p[i].second);
    sort(x, x + n);
    sort(p, p + n, [](pair<int, int> i, pair<int, int> j) {return i.first + i.second < j.first + j.second; });
    x[n] = p[n].first = 1e5;
    for (int i = 0; i < n; i++) {
        int sa = 0, sb = 0;
        for (int j = 0; j < n; j++) {
            if (max(p[j].first, p[j].second) <= x[i]) sa += p[j].first, sb += p[j].second;
            r += (long long)(sa > sb)*(p[j + 1].first + p[j + 1].second - p[j].first - p[j].second)*(x[i + 1] - x[i]);
        }
    }
    printf("%lld", r);
    return 0;
}