Submission #936331

#	Time	Username	Problem	Language	Result	Execution time	Memory
936331		LOLOLO	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	72 ms	4204 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 100 + 10;
ll dis[N][N], profit[N][N];
ll b[N][1000 + 10], s[N][1000 + 10], n;

ll bin(ll m) {
    vector < vector <ll>> dd(n + 1, vector <ll> (n + 1, -1e17));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dd[i][j] = profit[i][j] - dis[i][j] * m;
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dd[i][j] = max(dd[i][j], dd[i][k] + dd[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dd[i][i] >= 0) {
            return 1;
        }
    }

    return 0;
}

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

    for (int i = 1; i <= n; i++) {
        fill(dis[i], dis[i] + n + 1, 1e9);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> b[i][j] >> s[i][j];
        }
    }

    for (int i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        dis[a][b] = min(dis[a][b], c);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int f = 1; f <= k; f++) {
                if (s[j][f] == -1 || b[i][f] == -1)
                    continue;

                profit[i][j] = max(profit[i][j], s[j][f] - b[i][f]);
            }        
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }

    ll l = 0, r = 1e9 + 100, ans = 0;
    while (l <= r) {
        ll m = (l + r) / 2;
        if (bin(m)) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        //solve();
        cout << solve() << '\n';
    }
}

/*
4   5   2
10 9   5   2
6  4   20  15
9  7   10  9
-1 -1  16  11
1  2   3
2  3   3
1  4   1
4  3   1
3  1   1
*/

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