結果
問題 | No.453 製薬会社 |
ユーザー |
![]() |
提出日時 | 2016-12-04 01:21:47 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,429 bytes |
コンパイル時間 | 1,083 ms |
コンパイル使用メモリ | 85,932 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-27 19:35:20 |
合計ジャッジ時間 | 1,977 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 9 |
ソースコード
#include <algorithm> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <iostream> #include <queue> #include <list> #include <stack> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; class Simplex { int N; int M; std::vector< std::vector< double > > tbl; void pivot(int p, int q){ for(int j=0; j<=N; j++){ for(int k=M; k>=0; k--){ if(j != p && k != q){ tbl[j][k] -= tbl[p][k] * tbl[j][q] / tbl[p][q]; } } } for(int j=0; j<=N; j++){ if(j != p){ tbl[j][q] = 0; } } for(int k=0; k<=M; k++){ if(k != q){ tbl[p][k] = tbl[p][k] / tbl[p][q]; } } tbl[p][q] = 1; } public: Simplex(int N, int M): N(N), M(M), tbl(N+1, std::vector<double>(M+1, 0.0)) { if(N > M){ std::cerr << "check: N > M" << std::endl; } } int getN(){ return N; } int getM(){ return M; } double get(int i, int j){ if(0<=i && i<N+1 && 0<=j && j<M+1){ return tbl[i][j]; } return -999999.0; } void set(int i, int j, double val){ if(0<=i && i<N+1 && 0<=j && j<M+1){ tbl[i][j] = val; } } bool solve(){ int p, q; while(true){ for(q=0; (q<=M) && (tbl[0][q]>=0); q++); for(p=0; (p<=N) && (tbl[p][q]<=0); p++); if(q > M || p > N) break; //std::cerr << "!" << p << " " << q << std::endl; for(int i=p+1; i<=N; i++){ if(tbl[i][q] > 0){ if(tbl[i][M] / tbl[i][q] < tbl[p][M] / tbl[p][q]){ p = i; } } } pivot(p, q); } if(q == M+1) return true; if(p == N+1) return false; return false; } }; int main(){ double C, D; cin >> C >> D; Simplex smp(2, 4); smp.set(0, 0, -1000); smp.set(0, 1, -2000); smp.set(0, 2, 0); smp.set(0, 3, 0); smp.set(0, 4, 0); smp.set(1, 0, 3/4.0); smp.set(1, 1, 2/7.0); smp.set(1, 2, 1); smp.set(1, 3, 0); smp.set(1, 4, C); smp.set(2, 0, 1/4.0); smp.set(2, 1, 5/7.0); smp.set(2, 2, 0); smp.set(2, 3, 1); smp.set(2, 4, D); smp.solve(); printf("%.12lf\n", smp.get(0,4)); return 0; }