Submission #975498

#	Time	Username	Problem	Language	Result	Execution time	Memory
975498		colossal_pepe	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	84 ms	4228 KiB

merchant

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

using ll = long long;

const ll INF = 1e9;

int n, m, o;
vector<vector<ll>> b, s, d, p;

void precalc() {
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < n; i++) {
			for (int k = 0; k < n; k++) {
				if (i == k) continue;
				d[i][k] = min(d[i][k], d[i][j] + d[j][k]);
			}
		}
	}
	p.resize(n, vector<ll>(n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (d[i][j] == INF) continue;
			for (int k = 0; k < o; k++) {
				if (s[j][k] == -1 or b[i][k] == -1) continue;
				p[i][j] = max(p[i][j], s[j][k] - b[i][k]);
			}
		}
	}
}

ll solve() {
	ll lo = 0, hi = 1e9;
	auto ok = [](ll x) {
		vector<vector<ll>> dist(n, vector<ll>(n));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dist[i][j] = p[i][j] - d[i][j] * x;
			}
		}
		for (int j = 0; j < n; j++) {
			for (int i = 0; i < n; i++) {
				for (int k = 0; k < n; k++) {
					dist[i][k] = max(dist[i][k], dist[i][j] + dist[j][k]);
				}
			}
		}
		bool ret = 0;
		for (int i = 0; i < n; i++) {
			ret |= (dist[i][i] >= 0);
		}
		return ret;
	};
	while (hi - lo > 1) {
		ll mid = (lo + hi) / 2;
		if (ok(mid)) lo = mid;
		else hi = mid - 1;
	}
	if (ok(hi)) return hi;
	return lo;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> o;
	b.resize(n, vector<ll>(o)), s.resize(n, vector<ll>(o));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < o; j++) {
			cin >> b[i][j] >> s[i][j];
		}
	}
	d.resize(n, vector<ll>(n, INF));
	while (m--) {
		int u, v;
		ll w;
		cin >> u >> v >> w;
		d[u - 1][v - 1] = w;
	}
	precalc();
	cout << solve() << '\n';
	return 0;
}

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