結果
| 問題 | No.453 製薬会社 |
| コンテスト | |
| ユーザー |
 lmori
|
| 提出日時 | 2026-04-25 16:39:42 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 12,032 bytes |
| 記録 | |
| コンパイル時間 | 6,075 ms |
| コンパイル使用メモリ | 387,752 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-04-25 16:39:56 |
| 合計ジャッジ時間 | 7,316 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 9 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using lint = long long;
using mint = modint998244353;
using ull = unsigned long long;
using ld = long double;
using int128 = __int128_t;
#define all(x) (x).begin(), (x).end()
#define EPS 1e-8
#define uniqv(v) v.erase(unique(all(v)), v.end())
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) < (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) < (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define log(x) cout << x << endl
#define logfixed(x) cout << fixed << setprecision(10) << x << endl;
#define logy(bool) \
if (bool) { \
cout << "Yes" << endl; \
} else { \
cout << "No" << endl; \
}
ostream& operator<<(ostream& dest, __int128_t value) {
ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char* d = end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(ios_base::badbit);
}
}
return dest;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
}
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& set_var) {
for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
os << *itr;
++itr;
if (itr != set_var.end()) os << " ";
itr--;
}
return os;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& map_var) {
for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
os << itr->first << " -> " << itr->second << "\n";
}
return os;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& pair_var) {
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
void out() { cout << '\n'; }
template <class T, class... Ts>
void out(const T& a, const Ts&... b) {
cout << a;
((cout << ' ' << b), ...);
cout << '\n';
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
for (T& in : v) is >> in;
return is;
}
inline void in(void) { return; }
template <typename First, typename... Rest>
void in(First& first, Rest&... rest) {
cin >> first;
in(rest...);
return;
}
template <typename T>
bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
vector<lint> dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
vector<lint> dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<lint> dx4 = {1, 0, -1, 0};
vector<lint> dy4 = {0, 1, 0, -1};
bool equal_ld(long double a, long double b) {
return abs(a - b) <= EPS;
}
// a>b
bool greater_ld(long double a, long double b) {
return !equal_ld(a, b) and a > b;
}
bool less_ld(long double a, long double b) {
return !equal_ld(a, b) and a < b;
}
// maximize z
pair<long double, vector<long double>> simplex(vector<long double> z, vector<vector<long double>> A, vector<long double> B) {
int n = int(A.size());
int m = int(A[0].size());
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
A[i][j] = -A[i][j];
}
}
bool is_feasible = true;
long double min_b = 1.0;
int min_b_id = -1;
for (int i = 0; i < n; i++) {
if (less_ld(B[i], 0.0)) {
is_feasible = false;
if (less_ld(B[i], min_b)) {
min_b = B[i];
min_b_id = i;
}
}
}
vector<int> n_index(m), b_index(n);
iota(n_index.begin(), n_index.end(), 0);
iota(b_index.begin(), b_index.end(), m);
long double optimal_value = 0.0;
if (!is_feasible) {
for (int i = 0; i < n; i++) {
A[i].emplace_back(0.0);
}
n_index.emplace_back(n + m);
for (int i = 0; i < n; i++) {
if (less_ld(B[i], 0.0)) {
A[i][m] = 1.0;
if (i == min_b_id) {
B[i] = -B[i];
for (int j = 0; j < m; j++) {
A[i][j] = -A[i][j];
}
swap(b_index[i], n_index[m]);
}
}
}
for (int i = 0; i < n; i++) {
if (less_ld(B[i], 0.0) and i != min_b_id) {
B[i] += B[min_b_id];
for (int j = 0; j < m; j++) {
A[i][j] += A[min_b_id][j];
}
}
}
long double ap_optimal_value = min_b;
// maximize z_
vector<long double> z_(m + 1);
for (int j = 0; j <= m; j++) {
z_[j] = -A[min_b_id][j];
}
bool stop = false;
while (!stop) {
stop = true;
int min_j = 1e9;
int j_memo;
for (int j = 0; j <= m; j++) {
if (greater_ld(z_[j], 0.0) and min_j > n_index[j]) {
min_j = n_index[j];
j_memo = j;
stop = false;
}
}
if (min_j != 1e9) {
int j = j_memo;
if (greater_ld(z_[j], 0.0)) {
stop = false;
int min_i = 1e9;
int i_memo;
long double min_ratio = 1e18;
for (int i = 0; i < n; i++) {
if (less_ld(A[i][j], 0.0)) {
long double ratio = B[i] / (-A[i][j]);
if (greater_ld(min_ratio, ratio) or (equal_ld(min_ratio, ratio) and greater_ld(min_i, b_index[i]))) {
min_i = b_index[i];
i_memo = i;
min_ratio = ratio;
}
}
}
if (min_i == 1e9) {
// 非有界
return {1e35, {}};
} else {
vector<long double> tmp(m + 1);
long double coef = -A[i_memo][j];
for (int r = 0; r < n; r++) {
if (r == i_memo) {
for (int c = 0; c <= m; c++) {
if (c != j) {
tmp[c] = A[r][c] / coef;
} else {
tmp[c] = (-1.0) / coef;
}
}
B[r] /= coef;
continue;
}
long double mul = A[r][j];
if (equal_ld(mul, 0.0)) continue;
B[r] += mul * min_ratio;
for (int c = 0; c <= m; c++) {
if (c != j) {
A[r][c] += A[i_memo][c] / coef * mul;
} else {
A[r][c] = (-1.0) / coef * mul;
}
}
}
long double mul = z_[j];
ap_optimal_value += mul * min_ratio;
for (int c = 0; c <= m; c++) {
if (c != j) {
z_[c] += A[i_memo][c] / coef * mul;
} else {
z_[c] = (-1.0) / coef * mul;
}
}
swap(A[i_memo], tmp);
swap(n_index[j], b_index[i_memo]);
}
}
}
}
if (equal_ld(ap_optimal_value, 0.0)) {
for (int i = 0; i < n; i++) {
if (b_index[i] == n + m) {
for (int j = 0; j <= m; j++) {
if (!equal_ld(A[i][j], 0.0)) {
vector<long double> tmp(m + 1);
long double coef = -A[i][j];
long double ratio = B[i] / coef;
for (int r = 0; r < n; r++) {
if (r == i) {
for (int c = 0; c <= m; c++) {
if (c != j) {
tmp[c] = A[r][c] / coef;
} else {
tmp[c] = (-1.0) / coef;
}
}
B[r] = ratio;
continue;
}
long double mul = A[r][j];
if (equal_ld(mul, 0.0)) continue;
B[r] += mul * ratio;
for (int c = 0; c <= m; c++) {
if (c != j) {
A[r][c] += A[i][c] / coef * mul;
} else {
A[r][c] = (-1.0) / coef * mul;
}
}
}
long double mul = z_[j];
ap_optimal_value += mul * ratio;
for (int c = 0; c <= m; c++) {
if (c != j) {
z_[c] += A[i][c] / coef * mul;
} else {
z_[c] = (-1.0) / coef * mul;
}
}
swap(A[i], tmp);
swap(n_index[j], b_index[i]);
break;
}
}
}
}
for (int j = 0; j < m; j++) {
if (n_index[j] == n + m) {
for (int i = 0; i < n; i++) {
swap(A[i][j], A[i][m]);
A[i].pop_back();
}
swap(z_[j], z_[m]);
z_.pop_back();
swap(n_index[j], n_index[m]);
n_index.pop_back();
}
}
vector<int> rid(n + m, -1);
for (int i = 0; i < n; i++) {
rid[b_index[i]] = i;
}
for (int j = 0; j < m; j++) {
rid[n_index[j]] = n + j;
}
vector<long double> nz(m, 0.0);
for (int j = 0; j < m; j++) {
if (greater_ld(z[j], 0.0)) {
if (rid[j] < n) {
// basis
for (int c = 0; c < m; c++) {
nz[c] += A[rid[j]][c] * z[j];
}
optimal_value += B[rid[j]] * z[j];
} else {
// non-basis
nz[rid[j] - n] += z[j];
}
}
}
swap(z, nz);
} else {
// 実行不可能
return {-1e35, {}};
}
}
bool stop = false;
while (!stop) {
stop = true;
int min_j = 1e9;
int j_memo;
for (int j = 0; j < m; j++) {
if (greater_ld(z[j], 0.0) and min_j > n_index[j]) {
min_j = n_index[j];
j_memo = j;
stop = false;
}
}
if (min_j != 1e9) {
int j = j_memo;
if (greater_ld(z[j], 0.0)) {
int min_i = 1e9;
int i_memo;
long double min_ratio = 1e18;
for (int i = 0; i < n; i++) {
if (less_ld(A[i][j], 0.0)) {
long double ratio = B[i] / (-A[i][j]);
if (greater_ld(min_ratio, ratio) or (equal_ld(min_ratio, ratio) and greater_ld(min_i, b_index[i]))) {
min_i = b_index[i];
i_memo = i;
min_ratio = ratio;
}
}
}
if (min_i == 1e9) {
// 非有界
return {1e35, {}};
} else {
vector<long double> tmp(m);
long double coef = -A[i_memo][j];
for (int r = 0; r < n; r++) {
if (r == i_memo) {
for (int c = 0; c < m; c++) {
if (c != j) {
tmp[c] = A[r][c] / coef;
} else {
tmp[c] = (-1.0) / coef;
}
}
B[r] /= coef;
continue;
}
long double mul = A[r][j];
if (equal_ld(mul, 0.0)) continue;
B[r] += mul * min_ratio;
for (int c = 0; c < m; c++) {
if (c != j) {
A[r][c] += A[i_memo][c] / coef * mul;
} else {
A[r][c] = (-1.0) / coef * mul;
}
}
}
long double mul = z[j];
optimal_value += mul * min_ratio;
for (int c = 0; c < m; c++) {
if (c != j) {
z[c] += A[i_memo][c] / coef * mul;
} else {
z[c] = (-1.0) / coef * mul;
}
}
swap(A[i_memo], tmp);
swap(n_index[j], b_index[i_memo]);
}
}
}
}
return {optimal_value, {}};
}
int main() {
cin.tie(0)->sync_with_stdio(0);
vector<long double> z = {1000, 2000};
vector<vector<long double>> a = {{0.75, 2.0 / 7.0}, {0.25, 5.0 / 7.0}};
vector<long double> b(2);
in(b);
logfixed(simplex(z, a, b).first);
}