結果

問題 No.453 製薬会社
ユーザー Pachicobue
提出日時 2018-03-04 08:25:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,416 bytes
コンパイル時間 2,412 ms
コンパイル使用メモリ 204,108 KB
最終ジャッジ日時 2025-01-05 09:04:12
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using ld = long double;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz=" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

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


constexpr ll MOD = 1000000007LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;



struct Simplex {
    using T = ld;
    using Arr = vector<T>;
    using Mat = vector<Arr>;
    static constexpr T EPS = 1e-10;
    enum class Status {
        OPTIMAL,
        UNBOUND,
        NOSOLUTION,
        UNKNOWN,
    };
    // max  cx
    // s.t. Ax <= b (b>=0)
    //      x >= 0
    Simplex(const Mat& A, const Arr& b, const Arr& c) : N(A.size()), M(c.size()), table(N + 2, Arr(M + 2, 0)), x(M, 0), index(M + N + 1)
    {
        assert(A[0].size() == M);
        assert(b.size() == N);
        iota(index.begin(), index.end(), 0);
        L = N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                table[i][j] = -A[i][j];
            }
            table[i][M] = 1;
            table[i][M + 1] = b[i];
            if (table[L][M + 1] > table[i][M + 1]) {
                L = i;
            }
        }
        for (int j = 0; j < M; j++) {
            table[N][j] = c[j];
        }
        table[N + 1][M] = -1;
        solve();
    }

    Status getStatus() const
    {
        return status;
    }

    Arr getArg() const
    {
        return x;
    }

    T getValue() const
    {
        return ans;
    }

private:
    int N;
    int M;
    int L = 0;
    Status status = Status::UNKNOWN;
    Mat table;
    Arr x;
    T ans;
    vector<int> index;
    static bool LT(const T x, const T y)
    {
        return y - x > EPS;
    }
    static bool EQ(const T x, const T y)
    {
        return abs(x - y) < EPS;
    }
    static bool LE(const T x, const T y)
    {
        return x - y < EPS;
    }
    void solve()
    {
        for (int E = M + 1 - 1;;) {
            if (L < N) {
                swap(index[E], index[L + M + 1]);
                table[L][E] = 1 / table[L][E];
                for (int j = 0; j < M + 2; j++) {
                    if (j != E) {
                        table[L][j] *= -table[L][E];
                    }
                }
                for (int i = 0; i < N + 2; i++) {
                    if (i != L) {
                        for (int j = 0; j < M + 2; j++) {
                            if (j != E) {
                                table[i][j] += table[i][E] * table[L][j];
                            }
                        }
                        table[i][E] = table[i][E] * table[L][E];
                    }
                }
            }
            E = -1;
            for (int j = 0; j < M + 1; j++) {
                if (E < 0 or index[E] > index[j]) {
                    if (LT(0, table[N + 1][j]) or (EQ(table[N + 1][j], 0) and LT(0, table[N][j]))) {
                        E = j;
                    }
                }
            }
            if (E < 0) {
                break;
            }
            L = -1;
            for (int i = 0; i < N; i++) {
                if (LT(table[i][E], 0)) {
                    if (L < 0 or LE(table[L][M + 1] / table[L][E], table[i][M + 1] / table[i][E])) {
                        L = i;
                    }
                }
            }
            if (L < 0) {
                status = Status::UNBOUND;
                return;
            }
        }
        if (LT(table[N + 1][M + 1], 0)) {
            status = Status::NOSOLUTION;
            return;
        }
        for (int i = 0; i < N; i++) {
            if (index[M + 1 + i] < M) {
                x[index[M + 1 + i]] = table[i][M + 1];
            }
        }
        ans = table[N][M + 1];
    }
};



int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int C, D;
    cin >> C >> D;
    Simplex::Mat A{{21, 8}, {7, 20}};
    Simplex::Arr b{28.0 * C, 28.0 * D};
    Simplex::Arr c{1000, 2000};
    const Simplex::T ans = Simplex(A, b, c).getValue();
    cout << fixed << setprecision(15) << ans << "\n";
    return 0;
}
0