Submission #250817

#	Time	Username	Problem	Language	Result	Execution time	Memory
250817		receed	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	84 ms	4216 KiB

merchant

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 101, K = 1001;
ll inf = 1e15;
ll md[N][N], mx[N][N], b[N][K], s[N][K], g[N][N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, m, k, u, v, w;
    cin >> n >> m >> k;
    rep(i, n)
        rep(j, k) {
            cin >> b[i][j] >> s[i][j];
            if (b[i][j] < 0)
                b[i][j] = inf;
        }
    rep(i, n)
        rep(j, n) {
            md[i][j] = inf;
            rep(l, k)
                mx[i][j] = max(mx[i][j], s[j][l] - b[i][l]);
        }
    rep(i, m) {
        cin >> u >> v >> w;
        u--; v--;
        md[u][v] = min(md[u][v], w);
    }
    rep(i, n)
        rep(j, n)
            rep(l, n)
                md[j][l] = min(md[j][l], md[j][i] + md[i][l]);
    ll cl = 0, cr = 1e9, cm;
    while (cr - cl > 1) {
        cm = (cl + cr) / 2;
        rep(i, n)
            rep(j, n) {
                if (i == j || md[i][j] == inf)
                    g[i][j] = -inf;
                else
                    g[i][j] = mx[i][j] - cm * md[i][j];
            }
        rep(i, n)
            rep(j, n)
                rep(l, n)
                    g[j][l] = max(g[j][l], g[j][i] + g[i][l]);
        rep(i, n)
            if (g[i][i] >= 0)
                cl = cm;
        if (cl != cm)
            cr = cm;
    }
    cout << cl;
}

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