結果

問題 No.453 製薬会社
ユーザー glreto
提出日時 2021-04-16 20:43:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,450 bytes
コンパイル時間 1,471 ms
コンパイル使用メモリ 107,576 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 23:13:07
合計ジャッジ時間 2,160 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include<iomanip>
#include<functional>
#include<algorithm>
#include<deque>
#include<math.h>
#include<set>
#include<cstdio>
#include<string>
#include<queue>
#include<complex>
#include<numeric>
#include<stack>
#include<unordered_map>
#include<map>
#include <cassert>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define req(i,n) for(ll i = 1;i<=n;i++)
#define rrep(i,n) for(int i = n-1;i>=0;i--)
#define ALL(a) a.begin(),a.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
struct Simplex {
    using F = double;
    static constexpr F EPS = 1e-9;
    int N, M;
    vector<int> idx;vector<vector<F>> a;
    int i_ch, j_ch;
    void initialize(const vector<vector<F>>& A, const vector<F>& b, const vector<F>& c) {
        N = c.size(), M = A.size();
        a.assign(M + 2, vector<F>(N + 2));
        i_ch = M;
        rep(i,M) {
            rep(j,N) a[i][j] = -A[i][j];
            a[i][N] = 1, a[i][N + 1] = b[i];
            if (a[i_ch][N + 1] > a[i][N + 1]) i_ch = i;
        }rep(j,N) a[M][j] = c[j];
        a[M + 1][N] = -1;
        idx.resize(N + M + 1);iota(ALL(idx), 0);
    }void solve() {
        vector<int> jupd;
        for (j_ch = N;;) {
            if (i_ch < M) {
                swap(idx[j_ch], idx[i_ch + N + 1]);
                a[i_ch][j_ch] = 1 / a[i_ch][j_ch];
                jupd.clear();
                rep(j, N+2) {
                    if (j != j_ch) {
                        a[i_ch][j] *= -a[i_ch][j_ch];
                        if (abs(a[i_ch][j]) > EPS) jupd.push_back(j);
                    }
                }rep(i,M+2) {
                    if (abs(a[i][j_ch]) < EPS or i == i_ch) continue;
                    for (auto j : jupd) a[i][j] += a[i][j_ch] * a[i_ch][j];
                    a[i][j_ch] *= a[i_ch][j_ch];
                }
            }j_ch = -1;
            rep(j,N+1) {
                if (j_ch < 0 or idx[j_ch] > idx[j]) {
                    if (a[M + 1][j] > EPS or (abs(a[M + 1][j]) < EPS and a[M][j] > EPS)) j_ch = j;
                }
            }if (j_ch < 0) break;
            i_ch = -1;
            rep(i,M) {
                if (a[i][j_ch] < -EPS) {
                    if (i_ch < 0) {
                        i_ch = i;
                    }F com = a[i_ch][N + 1] / a[i_ch][j_ch] - a[i][N + 1] / a[i][j_ch];
                    if (com < -EPS) i_ch = i;
                    else if (com < EPS && idx[i_ch] > idx[i]) i_ch = i;
                }
            }if (i_ch < 0) {
                is_infty = 1;
                break;
            }
        }if (a[M + 1][N + 1] < -EPS) {
            infeasible = 1;
            return;
        }x.assign(N, 0);
        rep(i,M) {
            if (idx[N + 1 + i] < N) x[idx[N + 1 + i]] = a[i][N + 1];
        }ans = a[M][N + 1];
    }
    Simplex(const vector<vector<F>>& A, const vector<F>& b, const vector<F>& c) {
        is_infty = infeasible = false;
        initialize(A, b, c);
        solve();
    }bool is_infty,infeasible;
    vector<F> x;
    F ans;
};
int main() {
    double c, d; cin >> c >> d;
    vector<vector<double>> a = { {0.75,2.0/7.0},{0.25,5.0 / 7.0} };
    vector<double> b = { c,d }, C = { 1000,2000 };
    Simplex sim(a, b, C);
    cout <<fixed <<setprecision(10) << sim.ans << endl;
}
0