チームメンバーの選び方を全探索すると、選び方が最大で \(4.5 \times 10^9\) 個になるため TLE してしまいます。

最小値の最大値のような形の問題では、答えを二分探索し、「答えが \(x\) 以上になるか？」という判定問題に持ち込むと簡単になることがあります。
この判定問題について考えましょう。

各能力値は、\(x\) 以上かどうかにしか興味がないので、\(x\) 以上なら \(1\) 、\(x\) 未満なら \(0\) と圧縮することができます。すると、能力値の組としてあり得るものが \(2^5=32\) 種類しかなくなるので、重複を取り除いた後 \(3\) 人の選び方を全探索することができます。

計算量は、能力値の種類を \(M\) 、採用する人数を \(K\) 、二分探索の上限を \(X\) として、\(O((NM+2^{MK})\log X)\) です。

回答例 (C++)

#include <iostream>
#include <vector>
#include <array>
#include <set>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector A(N, array<int, 5>{});
    for(auto& a : A) for(int& i : a) cin >> i;
    int ok = 0, ng = 1000000001;
    auto check = [&](int x) -> bool {
        set<int> s;
        for(auto& a : A){
            int bit = 0;
            for(int i : a){
                bit <<= 1;
                bit |= i >= x;
            }
            s.insert(bit);
        }
        for(int x : s) for(int y : s) for(int z : s){
            if((x | y | z) == 31) return 1;
        }
        return 0;
    };
    while(abs(ok - ng) > 1){
        int cen = (ok + ng) / 2;
        (check(cen) ? ok : ng) = cen;
    }
    cout << ok << endl;
}

回答例 (Python)

N = int(input())
A = [tuple(map(int, input().split())) for i in range(N)]

def check(x):
    s = set()
    for a in A:
        s.add(sum(1 << i for i in range(5) if a[i] >= x))
    for x in s:
        for y in s:
            for z in s:
                if x | y | z == 31:
                    return True
    return False

ok = 0
ng = 10**9 + 1
while ng - ok > 1:
    cen = (ok + ng) // 2
    if check(cen):
        ok = cen
    else:
        ng = cen
print(ok)

DP解

チーム全体のパワーをチームメンバーのパワーの最大値とするのではなく、好きなチームメンバーを選んでその人のパワーを採用するものとします。他の能力値も同様にします。すると、以下の DP ができます。

\(dp[i][j][k] = {}\)(\(i\) 番目までのメンバー候補のうち \(j\) 人採用し、能力値の採用状況が \(k\) であるときの、採用した能力値の最小値としてありえる最大値)

計算量は \(O(NKM2^M)\) です。

回答例 (C++)
回答例 (Python)