結果

問題 No.1122 Plane Tickets
ユーザー hitonanodehitonanode
提出日時 2021-02-11 23:40:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 4,019 bytes
コンパイル時間 7,398 ms
コンパイル使用メモリ 322,132 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 10:35:57
合計ジャッジ時間 9,184 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 1 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 1 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 1 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 1 ms
5,376 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 1 ms
5,376 KB
testcase_42 AC 1 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 1 ms
5,376 KB
testcase_46 AC 2 ms
5,376 KB
testcase_47 AC 1 ms
5,376 KB
testcase_48 AC 2 ms
5,376 KB
testcase_49 AC 1 ms
5,376 KB
testcase_50 AC 1 ms
5,376 KB
testcase_51 AC 2 ms
5,376 KB
testcase_52 AC 1 ms
5,376 KB
testcase_53 AC 1 ms
5,376 KB
testcase_54 AC 2 ms
5,376 KB
testcase_55 AC 2 ms
5,376 KB
testcase_56 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

ソースコード

diff # 

#pragma once
#include <cmath>
#include <numeric>
#include <vector>

// CUT begin
// Maximize cx s.t. Ax <= b, x >= 0
// Implementation idea: https://kopricky.github.io/code/Computation_Advanced/simplex.html
// Refer to https://hitonanode.github.io/cplib-cpp/combinatorial_opt/simplex.hpp
template <typename Float = double, int DEPS = 30> struct Simplex {
    const Float EPS = Float(1.0) / (1LL << DEPS);
    int N, M;
    std::vector<int> idx;
    std::vector<std::vector<Float>> a;
    int i_ch, j_ch;

    void initialize(const std::vector<std::vector<Float>> &A, const std::vector<Float> &b, const std::vector<Float> &c) {
        N = c.size(), M = A.size();

        a.assign(M + 2, std::vector<Float>(N + 2));
        i_ch = M;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) a[i][j] = -A[i][j];
            a[i][N] = 1, a[i][N + 1] = b[i];
            if (a[i_ch][N + 1] > a[i][N + 1]) i_ch = i;
        }
        for (int j = 0; j < N; j++) a[M][j] = c[j];
        a[M + 1][N] = -1;

        idx.resize(N + M + 1);
        std::iota(idx.begin(), idx.end(), 0);
    }

    inline Float abs_(Float x) noexcept { return x > -x ? x : -x; }
    void solve() {
        std::vector<int> jupd;
        for (j_ch = N;;) {
            if (i_ch < M) {
                std::swap(idx[j_ch], idx[i_ch + N + 1]);
                a[i_ch][j_ch] = Float(1) / a[i_ch][j_ch];
                jupd.clear();
                for (int j = 0; j < N + 2; j++) {
                    if (j != j_ch) {
                        a[i_ch][j] *= -a[i_ch][j_ch];
                        if (abs_(a[i_ch][j]) > EPS) jupd.push_back(j);
                    }
                }
                for (int i = 0; i < M + 2; i++) {
                    if (abs_(a[i][j_ch]) < EPS or i == i_ch) continue;
                    for (auto j : jupd) a[i][j] += a[i][j_ch] * a[i_ch][j];
                    a[i][j_ch] *= a[i_ch][j_ch];
                }
            }

            j_ch = -1;
            for (int j = 0; j < N + 1; j++) {
                if (j_ch < 0 or idx[j_ch] > idx[j]) {
                    if (a[M + 1][j] > EPS or (abs_(a[M + 1][j]) < EPS and a[M][j] > EPS)) j_ch = j;
                }
            }
            if (j_ch < 0) break;

            i_ch = -1;
            for (int i = 0; i < M; i++) {
                if (a[i][j_ch] < -EPS) {
                    if (i_ch < 0) {
                        i_ch = i;
                    } else if (a[i_ch][N + 1] / a[i_ch][j_ch] - a[i][N + 1] / a[i][j_ch] < -EPS) {
                        i_ch = i;
                    } else if (a[i_ch][N + 1] / a[i_ch][j_ch] - a[i][N + 1] / a[i][j_ch] < EPS and idx[i_ch] > idx[i]) {
                        i_ch = i;
                    }
                }
            }
            if (i_ch < 0) {
                is_infty = true;
                break;
            }
        }
        if (a[M + 1][N + 1] < -EPS) {
            infeasible = true;
            return;
        }
        x.assign(N, 0);
        for (int i = 0; i < M; i++) {
            if (idx[N + 1 + i] < N) x[idx[N + 1 + i]] = a[i][N + 1];
        }
        ans = a[M][N + 1];
    }
    Simplex(const std::vector<std::vector<Float>> &A, const std::vector<Float> &b, const std::vector<Float> &c) {
        is_infty = infeasible = false;
        initialize(A, b, c);
        solve();
    }
    bool is_infty;
    bool infeasible;
    std::vector<Float> x;
    Float ans;
};
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <iostream>
#include <vector>
#define PROBLEM "https://yukicoder.me/problems/no/1122"
using namespace std;

int main() {
    using Float = boost::multiprecision::cpp_dec_float_50;
    vector<Float> B(5);
    for (auto &x : B) cin >> x;
    vector<vector<Float>> A{{1, 1, 1, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 1, 1, 1}, {1, 0, 0, 1, 1}, {1, 1, 0, 0, 1}};
    vector<Float> C(5, 1);
    Simplex<Float, 30> simplex(A, B, C);
    cout << llround(simplex.ans - 0.17) << '\n'; // I haven't proved yet this always returns correct answer.
}
0