結果
| 問題 | No.453 製薬会社 |
| コンテスト | |
| ユーザー |
 lmori
|
| 提出日時 | 2026-04-25 02:42:20 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 6,677 bytes |
| 記録 | |
| コンパイル時間 | 4,530 ms |
| コンパイル使用メモリ | 381,544 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-04-25 02:42:26 |
| 合計ジャッジ時間 | 5,548 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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-10
#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;
for (int i = 0; i < n; i++) {
if (less_ld(B[i], 0.0)) is_feasible = false;
}
vector<int> n_index(m), b_index(n);
iota(n_index.begin(), n_index.end(), 0);
iota(b_index.begin(), b_index.end(), m);
if (!is_feasible) {
// todo
}
bool stop = false;
long double optimal_value = 0.0;
while (!stop) {
stop = true;
for (int j = 0; j < m; j++) {
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);
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]);
// for (int r = 0; r < n; r++) {
// cout << "x(" << b_index[r] << ") = ";
// cout << B[r] << " ";
// for (int c = 0; c < m; c++) {
// cout << (A[r][c] >= 0.0 ? "+" : "") << A[r][c] << "x(" << n_index[c] << ") ";
// }
// out();
// }
// cout << "z = " << optimal_value << " ";
// for (int c = 0; c < m; c++) {
// cout << (z[c] >= 0.0 ? "+" : "") << z[c] << "x(" << n_index[c] << ") ";
// }
// out();
// out("===================================");
// out();
break;
}
}
}
}
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);
}