結果

問題 No.453 製薬会社
ユーザー T101010101T101010101
提出日時 2023-07-07 21:36:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,353 bytes
コンパイル時間 3,894 ms
コンパイル使用メモリ 268,484 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-28 22:35:30
合計ジャッジ時間 4,750 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,500 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2")

#include <bits/extc++.h>
// #include <atcoder/all>
// using namespace atcoder;
using namespace std;
using namespace __gnu_pbds;

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Bdouble = mp::number<mp::cpp_dec_float<128>>;

#define TO_STRING(var) # var
#define pb emplace_back
#define int ll
#define endl '\n'
#define sqrt __builtin_sqrtl

using ll = long long;
using ld = long double;
const ld PI = acos(-1);
const int INF = 1 << 30;
const ll INFL = 1LL << 61;
const int MOD = 998244353;
// const int MOD = 1000000007;

const ld EPS = 1e-10;

const vector<int> dx = {0, 1, 0, -1, 1, 1, -1, -1}; // → ↓ ← ↑ ↘ ↙ ↖ ↗
const vector<int> dy = {1, 0, -1, 0, 1, -1, -1, 1};

struct Edge {
    int from, to;
    int cost;
    Edge(int to, int cost) : from(-1), to(to), cost(cost) {}
    Edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
    Edge &operator=(const int &x) {
        to = x;
        return *this;
    }
};

__attribute__((constructor))
void constructor() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


vector<vector<ld>> ans;

const ld inf = 1. / 0.;
ld simplexMethodPD(ld c[], int n, ld b[], int m, ld A[]) {
    ld T[m + 1][n + m + 1];
    memset(T, 0, sizeof(T));
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            T[j][i] = A[j * n + i];
        }
        T[j][n + j] = 1;
        T[j][n + m] = b[j];
    }
    for (int i = 0; i < n; i++) {
        T[m][i] = c[i];
    }

    while (true) { 
        int p = 0, q = 0;
        for (int i = 0; i < n + m; i++) {
            if (T[m][i] <= T[m][p]) p = i;
        }
        for (int j = 0; j < m; j++) {
            if (T[j][n + m] <= T[q][n + m]) q = j;
        }
        ld t = min(T[m][p], T[q][n + m]);
        if (t >= -EPS) { // optimal
            for (int i = 0; i < m + 1; i++) {
                for (int j = 0; j < n + m + 1; j++) {
                    ans[i][j] = T[i][j];
                }
            }
            return -T[m][n + m];
        }

        if (t < T[q][n + m]) { // tight on c -> primal update
            for (int j = 0; j < m; j++) {
                if (T[j][p] >= EPS) {
                    if (T[j][p] * (T[q][n + m]-t) >= T[q][p] * (T[j][n + m]-t)) q = j;
                }
            }
            if (T[q][p] <= EPS) return inf; // primal infeasible
        } else { // tight on b -> dual update
            for (int i = 0; i < n + m + 1; i++) {
                T[q][i] *= -1;
            }
            for (int i = 0; i < n + m; i++) {
                if (T[q][i] >= EPS) {
                    if (T[q][i] * (T[m][p] - t) >= T[q][p] * (T[m][i] - t)) p = i;
                }
            }
            if (T[q][p] <= EPS) return -inf; // dual infeasible
        }
        for (int i = 0; i < n + m + 1; i++) {
            if (i != p) T[q][i] /= T[q][p];
        }
        T[q][p] = 1; // pivot(q,p)
        for (int j = 0; j < m + 1; j++) {
            if (j != q) {
                ld alpha = T[j][p];
                for (int i = 0; i < n + m + 1; i++) {
                    T[j][i] -= T[q][i] * alpha;
                }
            }
        }
    }
}

signed main() {
    int N = 2, M = 2;
    int C, D;
    cin >> C >> D;
    ld c[N];
    c[0] = -1000, c[1] = -2000;
    ld A[M * N];
    ld b[M];
    b[0] = C, b[1] = D;
    vector<vector<ld>> V = {
        {(ld)3. / 4., (ld)2. / 7.}, 
        {(ld)1. / 4., (ld)5. / 7.}
    };
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            A[j * N + i] = V[j][i];
        }
    }

    ans.assign(M + 1, vector<ld>(N + M + 1));
    cout << -simplexMethodPD(c, N, b, M, A) << endl;
}
0