結果

問題 No.1122 Plane Tickets
ユーザー square1001
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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