Submission #408169

#	Time	Username	Problem	Language	Result	Execution time	Memory
408169		abc864197532	Travelling Merchant (APIO17_merchant)	C++17	33 / 100	121 ms	1292 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cerr << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
};
#ifdef Doludu
#define test(args...) info(), abc("[" + string(#args) + "]", args)
#define owo
#else
#define test(args...)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 998244353, N = 1000001, logN = 20, K = 111;

int main () {
    owo;
    int n, m, k;
    cin >> n >> m >> k;
    vv <pii> a(n, k, mp(0, 0));
    for (int i = 0; i < n; ++i) for (int j = 0; j < k; ++j) cin >> a[i][j];
    vv <int> dis(n, n, 1e9 + 87);
    vv <long long> profit(n, n, 0);
    for (int i = 0; i < n; ++i) dis[i][i] = 0;
    for (int i = 0, u, v, w; i < m; ++i) {
        cin >> u >> v >> w, --u, --v;
        dis[u][v] = min(dis[u][v], w);
    }
    for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    }
    for (int t = 0; t < k; ++t) {
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
            if (a[i][t].X == -1 || a[j][t].X == -1) continue;
            profit[i][j] = max(profit[i][j], (long long)a[j][t].Y - a[i][t].X);
        }
    }
    auto chk = [&](long long x) {
        vv <long long> d(n, n, 1ll << 60);
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
            if (i == j) d[i][j] = 0;
            else {
                d[i][j] = x * dis[i][j] - profit[i][j];
            }
        }
        for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            if (i == j && i != k) {
                if (d[i][k] + d[k][j] <= 0) return true;
            }
        }
        // a / b >= x
        // a >= b * x
        // b * x - a <= 0
        return false;
    };
    long long l = 0, r = 1 << 30;
    while (r - l > 1) {
        long long mid = l + r >> 1;
        if (chk(mid)) l = mid;
        else r = mid;
    }
    assert(r != 1 << 30);
    cout << l << endl;
}
/*
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
 */

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:89:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         long long mid = l + r >> 1;
      |                         ~~^~~

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