結果

問題 No.1122 Plane Tickets
ユーザー fastmathfastmath
提出日時 2020-07-22 22:08:30
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,714 bytes
コンパイル時間 2,141 ms
コンパイル使用メモリ 134,400 KB
実行使用メモリ 5,708 KB
最終ジャッジ日時 2023-09-04 20:46:37
合計ジャッジ時間 3,975 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,628 KB
testcase_01 AC 2 ms
5,516 KB
testcase_02 AC 3 ms
5,536 KB
testcase_03 AC 2 ms
5,608 KB
testcase_04 AC 2 ms
5,508 KB
testcase_05 AC 2 ms
5,588 KB
testcase_06 AC 2 ms
5,584 KB
testcase_07 AC 2 ms
5,532 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 2 ms
5,564 KB
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 2 ms
5,612 KB
testcase_44 AC 2 ms
5,536 KB
testcase_45 AC 2 ms
5,556 KB
testcase_46 AC 2 ms
5,456 KB
testcase_47 WA -
testcase_48 AC 2 ms
5,516 KB
testcase_49 WA -
testcase_50 AC 2 ms
5,580 KB
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

const int maxn = 505;
const int maxm = 505;

const ld eps = 1e-9;

bool eq(ld a, ld b) {
    return fabsl(a - b) < eps;
}

//BEGIN_CODE
namespace Simplex {

ld D[maxm][maxn]; // [n+2][m+2]
int B[maxm];
int N[maxn];
ld x[maxn];
int n, m;

//x >= 0, Ax <= b, c^Tx -> max
void init(int _n, int _m, ld A[][maxn], ld *b, ld *c) {
    n = _n, m = _m;
    forn (i, m)
        forn (j, n)
            D[i][j] = -A[i][j];
    forn (i, m) {
        D[i][n] = 1;
        D[i][n + 1] = b[i];
    }
    forn (j, n) {
        D[m][j] = c[j];
        D[m + 1][j] = 0;
    }
    D[m][n + 1] = D[m][n] = D[m + 1][n + 1] = 0;
    D[m + 1][n] = -1;
    iota(B, B + m, n);
    iota(N, N + n, 0);
    N[n] = -1;
}

void pivot(int b, int nb) {
    assert(D[b][nb] != 0);
    ld q = 1. / -D[b][nb];
    D[b][nb] = -1;
    forn (i, n + 2)
        D[b][i] *= q;
    forn (i, m + 2) {
        if (i == b)
            continue;
        ld coef = D[i][nb];
        D[i][nb] = 0;
        forn (j, n + 2)
            D[i][j] += coef * D[b][j];
    }
    swap(B[b], N[nb]);
}

bool betterN(int f, int i, int j) {
    if (eq(D[f][i], D[f][j]))
        return N[i] < N[j];
    return D[f][i] > D[f][j];
}

bool betterB(int nb, int i, int j) {
    ld ai = D[i][n + 1] / D[i][nb];
    ld aj = D[j][n + 1] / D[j][nb];
    if (eq(ai, aj))
        return B[i] < B[j];
    return ai > aj;
}

bool simplex(int phase) {
    int f = phase == 1 ? m : m + 1;
    while (true) {
        int nb = -1;
        forn (i, n + 1) {
            if (N[i] == -1 && phase == 1)
                continue;
            if (nb == -1 || betterN(f, i, nb))
                nb = i;
        }
        if (D[f][nb] <= eps)
            return phase == 1;
        assert(nb != -1);

        int b = -1;
        forn (i, m) {
            if (D[i][nb] >= -eps)
                continue;
            if (b == -1 || betterB(nb, i, b))
                b = i;
        }
        if (b == -1)
            return false;
        pivot(b, nb);
        if (N[nb] == -1 && phase == 2)
            return true;
    }
}

ld solve() {
    int b = -1;
    forn (i, m) {
        if (b == -1 || D[i][n + 1] < D[b][n + 1])
            b = i;
    }
    assert(b != -1);
    if (D[b][n + 1] < -eps) {
        pivot(b, n);
        if (!simplex(2) || D[m + 1][n + 1] < -eps)
            return -infl;
    }
    if (!simplex(1))
        return infl;

    forn (i, n)
        x[i] = 0;
    forn (i, m)
        if (B[i] < n)
            x[B[i]] = D[i][n + 1];

    return D[m][n + 1];
}

} //Simplex
//END_CODE

ld a[maxm][maxn];
ld b[maxm];
ld c[maxn];

int main() {
    #ifdef LOCAL
    assert(freopen("simplex.in", "r", stdin));
    #else
    #endif
    /*
    int n, m;
    cin >> n >> m;
    forn (i, m) {
        forn (j, n)
            cin >> a[i][j];
        cin >> b[i];
    }
    forn (i, n)
        cin >> c[i];
    Simplex::init(n, m, a, b, c);
    cout << Simplex::solve() << '\n';
    forn (i, n)
        cerr << Simplex::x[i] << ' ';
    cerr << '\n';
    */


    int n = 5;
    vector <int> ar(n);
    for (int i = 0; i < n; ++i) 
        cin >> ar[i];

    int m = 5;
    for (int s = 0; s < n; ++s) {
        int sum = 0;
        for (int i = 0; i < 3; ++i) {
            int pos = (s - i + n) % n;
            a[s][pos] = 1;
        }   
        b[s] = ar[s];        
    }   
    for (int i = 0; i < n; ++i)
        c[i] = 1;

    Simplex::init(n, m, a, b, c);
    cout << (long long)Simplex::solve() << '\n';
}
0