結果
問題 | No.1122 Plane Tickets |
ユーザー |
![]() |
提出日時 | 2020-07-03 18:22:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 1,000 ms |
コード長 | 10,240 bytes |
コンパイル時間 | 1,153 ms |
コンパイル使用メモリ | 92,288 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 17:34:27 |
合計ジャッジ時間 | 3,082 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 55 |
ソースコード
#ifndef CLASS_MATRIX#define CLASS_MATRIX#include <vector>#include <cassert>#include <cstddef>#include <cstdint>#include <utility>template<class type>class matrix {private:std::size_t R, C;std::vector<type> val;public:matrix() : R(0), C(0), val(std::vector<type>()) {};matrix(std::size_t R_, std::size_t C_) : R(R_), C(C_), val(std::vector<type>(R* C)) {}matrix(std::size_t N_) : R(N_), C(N_), val(std::vector<type>(N_* N_)) {}type& entry(std::size_t r, std::size_t c) { return val[r * C + c]; }type entry(std::size_t r, std::size_t c) const { return val[r * C + c]; }static const matrix unit(std::size_t N) {matrix ret(N);for (std::size_t i = 0; i < N; ++i) {ret.entry(i, i) = type(1);}return ret;}matrix transpose() const {matrix ret(C, R);for (std::size_t i = 0; i < R; ++i) {for (std::size_t j = 0; j < C; ++j) {ret.val[j * R + i] = val[i * C + j];}}return ret;}bool operator==(const matrix& mat) const {if (R != mat.R || C != mat.C) return false;for (std::size_t i = 0; i < R * C; ++i) {if (val[i] != mat.val[i]) return false;}return true;}bool operator!=(const matrix& mat) const {if (R != mat.R || C != mat.C) return true;for (std::size_t i = 0; i < R * C; ++i) {if (val[i] != mat.val[i]) return true;}return false;}matrix& operator+=(const matrix& mat) {assert(R == mat.R && C == mat.C);for (std::size_t i = 0; i < R * C; ++i) val[i] += mat.val[i];return *this;}matrix& operator-=(const matrix& mat) {assert(R == mat.R && C == mat.C);for (std::size_t i = 0; i < R * C; ++i) val[i] -= mat.val[i];return *this;}matrix& operator*=(const matrix& mat) {assert(C == mat.R);matrix tmat = mat.transpose();std::vector<type> tmp(R * tmat.R);for (std::size_t i = 0; i < R; ++i) {for (std::size_t j = 0; j < tmat.R; ++j) {for (std::size_t k = 0; k < C; ++k) {tmp[i * tmat.R + j] += val[i * C + k] * tmat.val[j * tmat.C + k];}}}C = tmat.R;val = tmp;return *this;}matrix operator+=(const type& x) {for (std::size_t i = 0; i < R * C; ++i) val[i] += x;return *this;}matrix operator-=(const type& x) {for (std::size_t i = 0; i < R * C; ++i) val[i] -= x;return *this;}matrix operator*=(const type& x) {for (std::size_t i = 0; i < R * C; ++i) val[i] *= x;return *this;}matrix operator+(const matrix& mat) const { return matrix(*this) += mat; }matrix operator-(const matrix& mat) const { return matrix(*this) -= mat; }matrix operator*(const matrix& mat) const { return matrix(*this) *= mat; }matrix operator+(const type& x) const { return matrix(*this) += x; }matrix operator-(const type& x) const { return matrix(*this) -= x; }matrix operator*(const type& x) const { return matrix(*this) *= x; }matrix pow(std::uint64_t b) const {assert(R == C);matrix ans = unit(R), cur(*this);while (b != 0) {if (b & 1) ans *= cur;cur *= cur;b >>= 1;}return ans;}std::pair<matrix, matrix> gaussian_elimination(const matrix& mat) const {assert(R == mat.R);matrix lmat(*this), rmat(mat);std::size_t curpos = 0;for (std::size_t i = 0; i < R; ++i) {while (curpos < C) {std::size_t pos = std::size_t(-1);for (std::size_t j = i; j < R; ++j) {if (lmat.val[j * C + curpos] != type(0)) {pos = j;if (j != i) {for (std::size_t k = 0; k < C; ++k) std::swap(lmat.val[i * C + k], lmat.val[j * C + k]);for (std::size_t k = 0; k < rmat.C; ++k) std::swap(rmat.val[i * rmat.C + k], rmat.val[j * rmat.C + k]);}break;}}if (pos != std::size_t(-1)) {type mult = type(1) / lmat.val[i * C + curpos];for (std::size_t j = 0; j < C; ++j) lmat.val[i * C + j] *= mult;for (std::size_t j = 0; j < rmat.C; ++j) rmat.val[i * rmat.C + j] *= mult;lmat.val[i * C + curpos] = type(1);for (std::size_t j = 0; j < R; ++j) {if (j == i || lmat.val[j * C + curpos] == type(0)) continue;type submult = lmat.val[j * C + curpos];for (std::size_t k = 0; k < C; ++k) lmat.val[j * C + k] -= lmat.val[i * C + k] * submult;for (std::size_t k = 0; k < rmat.C; ++k) rmat.val[j * rmat.C + k] -= rmat.val[i * rmat.C + k] * submult;lmat.val[j * C + curpos] = type(0);}break;}++curpos;}if (curpos == C) break;}return std::make_pair(lmat, rmat);}matrix inverse() const {assert(R == C);std::pair<matrix, matrix> res = gaussian_elimination(unit(R));if (res.first != unit(R)) return matrix();return res.second;}type determinant() const {assert(R == C);matrix mat(*this);type ans = type(1);for (std::size_t i = 0; i < R; ++i) {std::size_t pos = std::size_t(-1);for (std::size_t j = i; j < R; ++j) {if (mat.val[j * C + i] != type(0)) {pos = j;break;}}if (pos == std::size_t(-1)) return type(0);if (pos != i) {ans *= type(-1);for (std::size_t j = i; j < C; ++j) {std::swap(mat.val[i * C + j], mat.val[pos * C + j]);}}ans *= mat.val[i * C + i];for (std::size_t j = i + 1; j < R; ++j) {type mul = mat.val[j * C + i] / mat.val[i * C + i];for (std::size_t k = i + 1; k < C; ++k) {mat.val[j * C + k] -= mat.val[i * C + k] * mul;}}}return ans;}};#endif // CLASS_MATRIXlong long gcd(long long x, long long y) {if (y == 0) return x;return gcd(y, x % y);}long long lcm(long long x, long long y) {return x / gcd(x, y) * y;}struct fraction {public:long long a, b;explicit fraction() : a(0), b(1) {};explicit fraction(long long a_) : a(a_), b(1) {};explicit fraction(long long a_, long long b_) {if (b_ < 0) a_ *= -1, b_ *= -1;long long g = gcd((a_ > 0 ? a_ : -a_), b_);a = a_ / b;b = b_ / b;};bool operator==(const fraction& f) { return a == f.a && b == f.b; }bool operator!=(const fraction& f) { return a != f.a || b != f.b; }fraction& operator+=(const fraction& f) {long long ca = 1LL * a * f.b + 1LL * b * f.a;long long cb = 1LL * b * f.b;long long g = gcd((ca > 0 ? ca : -ca), cb);a = ca / g;b = cb / g;return *this;}fraction& operator-=(const fraction& f) {long long ca = 1LL * a * f.b - 1LL * b * f.a;long long cb = 1LL * b * f.b;long long g = gcd((ca > 0 ? ca : -ca), cb);a = ca / g;b = cb / g;return *this;}fraction& operator*=(const fraction& f) {long long ca = 1LL * a * f.a, cb = 1LL * b * f.b;long long g = gcd((ca > 0 ? ca : -ca), cb);a = ca / g;b = cb / g;return *this;}fraction& operator/=(const fraction& f) {long long ca = 1LL * a * f.b, cb = 1LL * b * f.a;if (cb < 0) ca *= -1, cb *= -1;long long g = gcd((ca > 0 ? ca : -ca), cb);a = ca / g;b = cb / g;return *this;}fraction operator+(const fraction& f) const { return fraction(*this) += f; }fraction operator-(const fraction& f) const { return fraction(*this) -= f; }fraction operator*(const fraction& f) const { return fraction(*this) *= f; }fraction operator/(const fraction& f) const { return fraction(*this) /= f; }bool operator==(const fraction& f) const { return a == f.a && b == f.b; }bool operator!=(const fraction& f) const { return a != f.a || b != f.b; }bool operator<(const fraction& f) const { return (fraction(*this) - f).a < 0; }bool operator>(const fraction& f) const { return (fraction(*this) - f).a > 0; }bool operator<=(const fraction& f) const { return (fraction(*this) - f).a <= 0; }bool operator>=(const fraction& f) const { return (fraction(*this) - f).a >= 0; }};#include <string>#include <vector>#include <iostream>#include <algorithm>using namespace std;int main() {vector<long long> A(5);cin >> A[0] >> A[1] >> A[2] >> A[3] >> A[4];vector<vector<int> > base_mat = {{ 1, 0, 0, 1, 1 },{ 1, 1, 0, 0, 1 },{ 1, 1, 1, 0, 0 },{ 0, 1, 1, 1, 0 },{ 0, 0, 1, 1, 1 },};long long ans = 0;for (int i = 0; i < 1024; ++i) {int pcnt = 0;vector<int> sela, selb, selc;for (int j = 0; j < 10; ++j) {if ((i >> j) & 1) {++pcnt;if (j < 5) sela.push_back(j);else selb.push_back(j - 5);}else if (j < 5) {selc.push_back(j);}}if (pcnt != 5 || selb.size() == 0) continue;// 0 <= id <= 4: constraint x[id] = 0// 5 <= id <= 9: constraint sum(base_mat[id-5][i] * x[i]) = A[id - 5]int S = selb.size();matrix<fraction> mat(S);for (int j = 0; j < S; ++j) {for (int k = 0; k < S; ++k) {mat.entry(j, k) = fraction(base_mat[selb[j]][selc[k]]);}}matrix<fraction> imat = mat.inverse();if (imat == matrix<fraction>()) continue;int denom = 1;for (int j = 0; j < S; ++j) {for (int k = 0; k < S; ++k) {denom = lcm(denom, imat.entry(j, k).b);}}int max_improve = (denom - 1) * S;for (int j = 0; j <= max_improve; ++j) {string seq = string(j, 'o') + string(4, '|');do {vector<int> dec;int cont = 0;for (int k = 0; k <= seq.size(); ++k) {if (k == seq.size() || seq[k] == '|') {dec.push_back(cont);cont = 0;}else {++cont;}}bool valid = true;for (int k = 0; k < 5; ++k) {if (dec[k] > A[k]) {valid = false;}}if (!valid) continue;vector<fraction> val(S);for (int k = 0; k < S; ++k) {for (int l = 0; l < S; ++l) {val[k] += imat.entry(k, l) * fraction(A[selb[l]] - dec[selb[l]]);}}bool correct = true;for (int k = 0; k < S; ++k) {if (val[k] < fraction(0) || val[k].b != 1) {correct = false;}}if (!correct) continue;vector<long long> true_val(5);for (int k = 0; k < S; ++k) {true_val[selc[k]] = val[k].a;}bool fully_correct = true;for (int k = 0; k < 5; ++k) {long long sum = 0;for (int l = 0; l < 5; ++l) {sum += base_mat[k][l] * true_val[l];}if (sum > A[k]) {fully_correct = false;}}if (fully_correct) {long long score = 0;for (int k = 0; k < S; ++k) {score += val[k].a;}ans = max(ans, score);}} while (next_permutation(seq.begin(), seq.end()));}}cout << ans << endl;return 0;}