結果

問題 No.453 製薬会社
ユーザー T101010101T101010101
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0