結果
問題 | No.453 製薬会社 |
ユーザー | souta-1326 |
提出日時 | 2021-08-20 17:37:44 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 6,761 bytes |
コンパイル時間 | 2,466 ms |
コンパイル使用メモリ | 206,880 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-21 22:20:33 |
合計ジャッジ時間 | 3,123 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; const ll inf = 10000000000; template<class T> class frac{ T bunsi,bunbo; constexpr void setting() noexcept { T g = gcd(bunsi,bunbo); bunsi /= g;bunbo /= g; if(bunbo < 0){ bunsi = -bunsi;bunbo = -bunbo; } } public: constexpr frac(T Bunsi = 0,T Bunbo = 1) noexcept { bunsi = Bunsi;bunbo = Bunbo; setting(); } constexpr T &Bunsi() noexcept {return bunsi;} constexpr const T &Bunsi() const noexcept {return bunsi;} constexpr T &Bunbo() noexcept {return bunbo;} constexpr const T &Bunbo() const noexcept {return bunbo;} constexpr frac<T> &operator+=(const frac<T> &rhs) noexcept { bunsi = bunsi*rhs.bunbo+bunbo*rhs.bunsi; bunbo *= rhs.bunbo; setting(); return *this; } constexpr frac<T> &operator-=(const frac<T> &rhs) noexcept { bunsi = bunsi*rhs.bunbo-bunbo*rhs.bunsi; bunbo *= rhs.bunbo; setting(); return *this; } constexpr frac<T> &operator*=(const frac<T> &rhs) noexcept { bunbo *= rhs.bunbo; bunsi *= rhs.bunsi; setting(); return *this; } constexpr frac<T> &operator/=(const frac<T> &rhs) noexcept { bunbo *= rhs.bunsi; bunsi *= rhs.bunbo; setting(); return *this; } constexpr frac<T> &operator+=(const T rhs) noexcept { bunsi = bunsi+bunbo*rhs; setting(); return *this; } constexpr frac<T> &operator-=(const T rhs) noexcept { bunsi = bunsi-bunbo*rhs; setting(); return *this; } constexpr frac<T> &operator*=(const T rhs) noexcept { bunsi *= rhs; setting(); return *this; } constexpr frac<T> &operator/=(const T rhs) noexcept { bunbo *= rhs; setting(); return *this; } constexpr frac<T> operator+(const frac<T> &rhs) const noexcept {return frac(*this) += rhs;} constexpr frac<T> operator-(const frac<T> &rhs) const noexcept {return frac(*this) -= rhs;} constexpr frac<T> operator*(const frac<T> &rhs) const noexcept {return frac(*this) *= rhs;} constexpr frac<T> operator/(const frac<T> &rhs) const noexcept {return frac(*this) /= rhs;} constexpr frac<T> operator+(const T rhs) const noexcept {return frac(*this) += rhs;} constexpr frac<T> operator-(const T rhs) const noexcept {return frac(*this) -= rhs;} constexpr frac<T> operator*(const T rhs) const noexcept {return frac(*this) *= rhs;} constexpr frac<T> operator/(const T rhs) const noexcept {return frac(*this) /= rhs;} constexpr bool operator<(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo < bunbo*rhs.bunsi;} constexpr bool operator>(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo > bunbo*rhs.bunsi;} constexpr bool operator>=(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo >= bunbo*rhs.bunsi;} constexpr bool operator<=(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo <= bunbo*rhs.bunsi;} constexpr bool operator==(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo == bunbo*rhs.bunsi;} constexpr bool operator!=(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo != bunbo*rhs.bunsi;} constexpr bool operator<(const T rhs) const noexcept {return bunsi < bunbo*rhs;} constexpr bool operator>(const T rhs) const noexcept {return bunsi > bunbo*rhs;} constexpr bool operator<=(const T rhs) const noexcept {return bunsi <= bunbo*rhs;} constexpr bool operator>=(const T rhs) const noexcept {return bunsi >= bunbo*rhs;} constexpr bool operator==(const T rhs) const noexcept {return bunsi == bunbo*rhs;} constexpr bool operator!=(const T rhs) const noexcept {return bunsi != bunbo*rhs;} }; template<class T> void print(frac<T> &f){ cout << f.Bunsi() << "/" << f.Bunbo() << endl; } using F = long double; pair<F,vector<F>> Simplex_Method(ll N,ll M,vector<F> C,vector<vector<F>> A,vector<F> B){ assert(C.size() == N && A.size() == M && B.size() == M); for(int i=0;i<M;i++) assert(A[i].size() == N); F Ans = 0;//最大値 vector<F> X(N);//最大値を取る数列x //スラック変数を導入する //M個の条件に対し1つずつスラック変数を用意するので、スラック変数をM個追加 X.resize(N+M); C.resize(N+M); for(int i=0;i<M;i++) A[i].resize(N+M); //スラック変数を初期化 X[N+i]=B[i],A[i][N+i]=1 for(int i=0;i<M;i++) X[N+i] = B[i]; for(int i=0;i<M;i++) A[i][N+i] = 1; //スラック変数であるならば条件のindex,なければ-1 vector<int> Slack(N+M,-1); for(int i=0;i<M;i++) Slack[N+i] = i; //i番目の条件のスラック変数のindex vector<int> A_Slack(M); for(int i=0;i<M;i++) A_Slack[i] = N+i; //操作ができるまで while(true){ //正の係数をとる非スラック変数を探す int target = -1; for(int i=0;i<N+M;i++){ if(Slack[i] == -1 && C[i] > 0){ target = i;break; } } //もしすべての係数が正でなかったら、操作を終了 if(target == -1) break; //スラック変数の余裕がある限りX[target]を増やす //各条件で増やせる量のminを取れば良い //targetと、minを取る条件のスラック変数をswapするので、その条件のindexも記録する //いくらでも増やせる場合、infを返し操作を終了 F minval = inf; int minitr = -1; for(int i=0;i<M;i++){ if(A[i][target] <= 0) continue; if(B[i]/A[i][target] < minval){ minval = B[i]/A[i][target]; minitr = i; } } if(minval == inf){ Ans = inf;break; } //A[minitr]以外の条件式に対して変更を行う for(int i=0;i<M;i++){ if(i == minitr || A[i][target] == 0) continue; F propo = A[i][target]/A[minitr][target]; //B[i]の値を変更 B[i] -= B[minitr]*propo; //スラック変数の値を変更 X[A_Slack[i]] = B[i]/A[i][A_Slack[i]]; //A[i]の各値を変更 for(int j=0;j<N+M;j++){ A[i][j] -= A[minitr][j]*propo; } } //最大化式も変更 F propo = C[target]/A[minitr][target]; Ans += B[minitr]*propo; for(int j=0;j<N+M;j++){ C[j] -= A[minitr][j]*propo; } //最後にスラック変数をSwap X[target] = B[minitr]/A[minitr][target]; X[A_Slack[minitr]] = 0; Slack[target] = minitr; Slack[A_Slack[minitr]] = -1; A_Slack[minitr] = target; } //出力 vector<F> SubX; copy(X.begin(),X.begin()+N,back_inserter(SubX)); return make_pair(Ans,SubX); } int main(){ cout << fixed << setprecision(10); int C,D;cin >> C >> D; int N = 2,M = 2; vector<F> Ma({1000,2000}); vector<vector<F>> A({{F(3)/4,F(2)/7},{F(1)/4,F(5)/7}}); vector<F> B({F(C),F(D)}); auto ret = Simplex_Method(N,M,Ma,A,B); F ans = ret.first; cout << ans << endl; }