Submission #1125478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125478		KenIsGenius	Travelling Merchant (APIO17_merchant)	C++20	33 / 100	52 ms	2116 KiB

merchant

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define pob pop_back
#define SZ(x) (int)(x.size())
#define all(x) begin(x), end(x)
#ifdef LOCAL
#define HEHE freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define HEHE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 7122;
#endif
using namespace std;
 
#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)
 
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }

#define int long long

const int MAXN = 105;
int n;
void floyd(int G[MAXN][MAXN]) {
    FOR (i, 1, n) FOR (j, 1, n) 
        FOR (k, 1, n)
            chmin(G[i][j], G[i][k] + G[k][j]);
}
const int inf = (1ll << 60) - 1;
int m, k;
int G[MAXN][MAXN], profit[MAXN][MAXN];
int G2[MAXN][MAXN];
int b[MAXN][1005], s[MAXN][1005];
signed main() {
    HEHE
    cin >> n >> m >> k;
    FOR (i, 1, n) {
        FOR (j, 1, k) {
            cin >> b[i][j] >> s[i][j];
        }
    }
    FOR (i, 1, n) {
        FOR (j, 1, n) {
            G[i][j] = inf;
            // profit[i][j] = -1e9;
        }
    }
    FOR (i, 1, m) {
        int u, v, w; cin >> u >> v >> w;
        chmin(G[u][v], w);
    }
    floyd(G);
    FOR (i, 1, n) {
        FOR (j, 1, n) {
            FOR (x, 1, k)
                if (s[j][x] != -1 and b[i][x] != -1)
                    chmax(profit[i][j], s[j][x] - b[i][x]);
        }
    }
    // profit / len >= x
    // x * len - profit <= 0
    int l = 0, r = 1e9 + 10;
    while (l < r - 1) {
        int mid = (l + r) / 2;
        FOR (i, 1, n) {
            FOR (j, 1, n) {
                G2[i][j] = mid * min(G[i][j], inf/mid) - profit[i][j];
                chmin(G2[i][j], inf);
            }
        }
        floyd(G2);
        int ok = 0;
        FOR (i, 1, n) {
            if (G2[i][i] <= 0) ok = 1;
        }
        if (ok) l = mid;
        else r = mid;
    }
    cout << l << '\n';
}

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