oj.uz

Submission #213524

# Submission time Handle Problem Language Result Execution time Memory
213524 2020-03-26T04:13:33 Z tri Travelling Merchant (APIO17_merchant) C++14
0 / 100
 212 ms 4088 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


const int MAXN = 105;
const int MAXK = 1005;
const ll INF = 1e10;

ll aM[MAXN][MAXN];

ll trans[2][MAXN][MAXK]; // 0 is buy 1 is sell

ll prof[MAXN][MAXN];

ld agg[MAXN][MAXN];

ld best[MAXN];

int N, M, K;

bool pos(ld ef) {
    assert(ef > 0);
//    ps(ef);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            agg[i][j] = prof[i][j] - aM[i][j] * ef;
        }
    }

    fill(best, best + MAXN, 0);

    for (int i = 0; i < N; i++) {
        for (int cV = 0; cV < N; cV++) {
            for (int aV = 0; aV < N; aV++) {
                if (best[aV] < best[cV] + agg[cV][aV]) {
                    best[aV] = best[cV] + agg[cV][aV];
                }
            }
        }
    }

    for (int cV = 0; cV < N; cV++) {
        for (int aV = 0; aV < N; aV++) {
            if (best[aV] < best[cV] + agg[cV][aV]) {
                return true;
            }
        }
    }
    return false;
}

ll binSearch() {
    ll low = 0;
    ll hi = INF;
    while (low != hi) {
        ll mid = (low + hi + 1) / 2;
        if (pos(mid)) {
            low = mid;
        } else {
            hi = mid - 1;
        }
    }

    if (pos(low + 1 - 1e-12)) {
        return low + 1;
    }

    return low;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++) {
            cin >> trans[0][i][j] >> trans[1][i][j];
            if (trans[0][i][j] == -1) {
                trans[0][i][j] = INF;
            }
            if (trans[1][i][j] == -1) {
                trans[1][i][j] = -INF;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            aM[i][j] = INF;
        }
    }

//    ps("here");

    for (int i = 0; i < M; i++) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        u--, v--;
        aM[u][v] = c;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                if (aM[j][i] + aM[i][k] < aM[j][k]) {
                    aM[j][k] = aM[j][i] + aM[i][k];
                }
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ll cM = 0;
            for (int k = 0; k < K; k++) {
                cM = max(cM, trans[1][j][k] - trans[0][i][k]);
            }
            prof[i][j] = cM;
        }
    }

//    cout << pos(2) << endl;

    ll ans = binSearch();
    cout << ans << endl;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 2296 KB Output is correct
2 Correct 171 ms 1536 KB Output is correct
3 Correct 177 ms 1536 KB Output is correct
4 Correct 27 ms 896 KB Output is correct
5 Correct 26 ms 896 KB Output is correct
6 Correct 27 ms 896 KB Output is correct
7 Correct 27 ms 1024 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 27 ms 896 KB Output is correct
10 Incorrect 27 ms 896 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 896 KB Output is correct
2 Correct 27 ms 896 KB Output is correct
3 Correct 28 ms 1024 KB Output is correct
4 Correct 25 ms 1024 KB Output is correct
5 Correct 28 ms 1024 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 28 ms 1016 KB Output is correct
8 Correct 27 ms 1024 KB Output is correct
9 Correct 27 ms 896 KB Output is correct
10 Correct 27 ms 1024 KB Output is correct
11 Correct 28 ms 1024 KB Output is correct
12 Incorrect 27 ms 1024 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 1664 KB Output is correct
2 Correct 212 ms 4088 KB Output is correct
3 Correct 175 ms 1664 KB Output is correct
4 Correct 183 ms 1920 KB Output is correct
5 Incorrect 178 ms 1920 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 896 KB Output is correct
2 Correct 27 ms 896 KB Output is correct
3 Correct 28 ms 1024 KB Output is correct
4 Correct 25 ms 1024 KB Output is correct
5 Correct 28 ms 1024 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 28 ms 1016 KB Output is correct
8 Correct 27 ms 1024 KB Output is correct
9 Correct 27 ms 896 KB Output is correct
10 Correct 27 ms 1024 KB Output is correct
11 Correct 28 ms 1024 KB Output is correct
12 Incorrect 27 ms 1024 KB Output isn't correct
13 Halted 0 ms 0 KB -