Submission #1159789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159789		ProtonDecay314	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	62 ms	2112 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
#define pb push_back
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()

const ll BUY_MAX = 1'000'000'000ll;
const ll SELL_MIN = 0ll;
const ll INT_INF = (ll)INF(int);

/*
check if the graph with weights M*dur - profit
has a nonpositive cycle
*/
bool good(ll n, ll m, ll k, ll M, const vvll& dur, const vvll& profits) {
    vvll dist;
    for(ll i = 0ll; i < n; i++) {
        vll distr(n, INT_INF);
        dist.pb(distr);
    }

    // Initialize distance array

    for(ll i = 0ll; i < n; i++) {
        for(ll j = 0ll; j < n; j++) {
            if(i == j) continue;

            dist[i][j] = M * dur[i][j] - profits[i][j];
        }
    }

    // Apply Floyd-warshall

    for(ll i = 0ll; i < n; i++) {
        for(ll j = 0ll; j < n; j++) {
            for(ll k = 0ll; k < n; k++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for(ll i = 0ll; i < n; i++) {
        for(ll j = 0ll; j < n; j++) {
            for(ll k = 0ll; k < n; k++) {
                if(dist[i][k] + dist[k][j] < dist[i][j]) {
                    // Found negative cycle, return
                    return true;
                }
            }
        }
    }

    for(ll i = 0ll; i < n; i++) if(dist[i][i] == 0ll) return true;
    return false;
}

int main() {
    ll n, m, k;
    cin >> n >> m >> k;

    // Input the prices
    vvpll market;
    for(ll i = 0ll; i < n; i++) {
        vpll prices;
        for(ll j = 0ll; j < k; j++) {
            ll b, s;
            cin >> b >> s;

            if(b == -1ll) b = BUY_MAX;
            if(s == -1ll) s = SELL_MIN;

            prices.pb({b, s});
        }

        market.pb(prices);
    }

    // Input the weights in the adjacency matrix
    vvll dist;
    for(ll i = 0ll; i < n; i++) {
        vll distr(n, INT_INF);
        dist.pb(distr);
    }

    for(ll i = 0ll; i < n; i++) dist[i][i]= 0ll;

    for(ll i = 0ll; i < m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;

        dist[u][v] = w;
    }

    for(ll i = 0ll; i < n; i++) {
        for(ll j = 0ll; j < n; j++) {
            if(i == j) continue;
            for(ll k = 0ll; k < n; k++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    // Preprocess shortest paths and max profits
    vvll profits;
    for(ll i = 0ll; i < n; i++) {
        vll profitsr(n, 0ll);
        profits.pb(profitsr);
    }

    // profits[buy][sell]
    for(ll i = 0ll; i < n; i++) {
        for(ll j = 0ll; j < n; j++) {
            if(i == j) continue;

            for(ll kp = 0ll; kp < k; kp++) {
                profits[i][j] = max(profits[i][j], market[j][kp].second - market[i][kp].first);
            }
        }
    }

    /// Shortest paths
    ll l = -1ll, r = INT_INF;

    while(r - l > 1ll) {
        ll M = (l + r) >> 1ll;

        if(good(n, m, k, M, dist, profits)) l = M;
        else r = M;
    }

    cout << max(l, 0ll) << endl;

    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34