結果
問題 | No.453 製薬会社 |
ユーザー |
|
提出日時 | 2023-07-07 21:36:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 4,353 bytes |
コンパイル時間 | 3,066 ms |
コンパイル使用メモリ | 260,380 KB |
最終ジャッジ日時 | 2025-02-15 06:54:10 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 9 |
ソースコード
// #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_sqrtlusing 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) { // optimalfor (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 updatefor (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 updatefor (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;}