AtCoder Grand Contest 012: A - AtCoder Group Contest

solution

貪欲。$O(N \log N)$。

強さが$x_1 \le x_2 \le x_3, \; y_1 \le y_2 \le y_3$な組$(x_1, x_2, x_3), \; (y_1, y_2, y_3)$があるとする。不等式を保ったまま適当に組み換えて$\max \{ x_1, y_1 \} \le \min \{ x_2, y_2 \}$にできて、このとき$x_2 + y_2$が最大で$y_3 \le x_2 \lor x_3 \le y_2$となる。 つまり長さが$3N$のとき、sortした後に組$(a_1, a_{3N-1}, a_{3N})$で作るのが最善。

implementation

#include <algorithm>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

int main() {
    int n; scanf("%d", &n);
    vector<int> a(3*n); repeat (i, 3*n) scanf("%d", &a[i]);
    whole(sort, a);
    ll result = 0;
    repeat (i, n) {
        result += a[3*n-1 - (2*i+1)];
    }
    printf("%lld\n", result);
    return 0;
}