#1184142 (C++23(gcc16)) No.3674 Zero Sum Game

• 問題: No.3674 Zero Sum Game
• ユーザー: ei1333333
• 提出日時: 2026-09-05 20:56:45
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,647 bytes
• コンパイル時間: 7,661 ms
• コンパイル使用メモリ: 390,820 KB
• 実行使用メモリ: 9,716 KB
• 最終ジャッジ日時: 2026-09-05 20:57:10
• 合計ジャッジ時間: 15,170 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	TLE * 1 -- * 38

ソースコード

#line 1 "template/template.hpp"
#include <bits/stdc++.h>

#if __has_include(<atcoder/all>)
#include <atcoder/all>

#endif

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (size_t i = 0; i < v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}

template <typename T1, typename T2>
bool chmax(T1& a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
bool chmin(T1& a, T2 b) {
  return a > b && (a = b, true);
}

template <typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
enable_if_t<is_class_v<T> == 0> fill_v(T& t, const V& v) {
  t = v;
}

template <typename T, typename V>
enable_if_t<is_class_v<T> != 0> fill_v(T& t, const V& v) {
  for (auto& e : t) fill_v(e, v);
}

template <typename F>
struct FixPoint : F {
  explicit FixPoint(F&& f) : F(std::forward<F>(f)) {}

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
decltype(auto) MFP(F&& f) {
  return FixPoint<F>{std::forward<F>(f)};
}


#define EPS 1e-10

// max c * x s.t. A*x <= b, x >= 0
class Simplex {
private:
    using Arr = vector<double>;
    using Mat = vector<vector<double> >;
    int* index;
    double** a;
    int row, column, L;

    void Set(const Mat& A, const Arr& b, const Arr& c){
        infinity = none = false;
        row = A.size(),column = A[0].size() + 1;
        index = new int[row + column];
        int i, j;
        for(i = 0; i < row + column; i++) index[i] = i;
        L = row;
        a = new double*[row + 2];
        for(i = 0; i < row + 2; i++) a[i] = new double[column + 1];
        for(i = 0; i < row; i++){
            for(j = 0; j < column - 1; j++) a[i][j] = -A[i][j];
            a[i][column-1] = 1, a[i][column] = b[i];
            if(a[L][column] > a[i][column]) L = i;
        }
        for(j = 0; j < column - 1; j++) a[row][j] = c[j];
        a[row+1][column-1] = -1;
    }

    void solve(){
        int E, i, j;
        int* ls = new int[column + 2];
        for(E = column - 1;;){
    	    if(L < row){
                swap(index[E], index[L + column]);
                a[L][E] = 1 / a[L][E];
                int prv = column + 1;
                for(j = 0; j < column + 1; j++){
                    if(j != E){
                        a[L][j] *= -a[L][E];
                        if(abs(a[L][j]) > EPS) ls[prv] = j, prv = j;
                    }
                }
                ls[prv] = column + 1;
                for(i = 0; i < row + 2; i++){
                    if(abs(a[i][E]) < EPS || i == L) continue;
                    for(j = ls[column + 1]; j < column + 1; j = ls[j]){
                        a[i][j] += a[i][E] * a[L][j];
                    }
                    a[i][E] *= a[L][E];
                }
    	    }
    	    E = -1;
            // double pre = EPS;
    	    for(j = 0; j < column; j++){
                if(E < 0 || index[E] > index[j]){
                    if(a[row + 1][j] > EPS || (abs(a[row + 1][j]) < EPS && a[row][j] > EPS)) E = j;
                    // if(a[row + 1][j] > pre) E = j, pre = a[row + 1][j];
                    // else if(abs(a[row + 1][j]) < EPS && a[row][j] > pre) E = j, pre = a[row][j];
                }
            }
            if(E < 0) break;
            L = -1;
            for(i = 0; i < row; i++){
                if(a[i][E] < -EPS){
                    if(L < 0) L = i;
                    else if(a[L][column] / a[L][E] - a[i][column] / a[i][E] < -EPS) L = i;
                    else if(a[L][column] / a[L][E] - a[i][column] / a[i][E] < EPS && index[L] > index[i]) L = i;
                    // if(L < 0 || a[L][column] / a[L][E] - a[i][column] / a[i][E] < EPS) L = i;
                }
            }
            if(L < 0){
                infinity = true;
                return;
            }
        }
        if(a[row + 1][column] < -EPS){
            none = true;
            return;
        }
        x.assign(column - 1, 0);
        for(i = 0; i < row; i++){
            if(index[column + i] < column - 1) x[index[column + i]] = a[i][column];
        }
        ans = a[row][column];
    }
public:
    bool infinity, none;
    double ans;
    Arr x;
    Simplex(const Mat& A, const Arr& b, const Arr& c){
        Set(A,b,c);
        solve();
    }
};

void sub() {
  int N, M;
  cin >> N >> M;
  const int S = 10001;
  auto A = make_v< double >(N, N);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      int x;
      cin >> x;
      A[i][j] = x + S;
    }
  }
  vector< double > b(N, 1.0), c(N, 1.0);
  Simplex sp(A, b, c);
  cout << 1.0 / sp.ans - S << endl;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    sub();
  }
}