Submission #824770

#	Time	Username	Problem	Language	Result	Execution time	Memory
824770		Alan	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	27 ms	3404 KiB

merchant

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

ll di[105][105], gain[105][105], b[105][1005], s[105][1005];
pair<ll, ll> opt[105][105];
const ll inf = 1e18;

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) di[i][j] = inf;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= k; j++) {
		cin >> b[i][j] >> s[i][j];
		if (b[i][j] == -1) b[i][j] = inf;
		if (s[i][j] == -1) s[i][j] = -inf;
	}
	while (m--) {
		int u, v;
		ll t;
		cin >> u >> v >> t;
		di[u][v] = t;
	}
	for (int t = 1; t <= n; t++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) di[i][j] = min(di[i][j], di[i][t] + di[t][j]);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
		gain[i][j] = 0;
		for (int a = 1; a <= k; a++) gain[i][j] = max(gain[i][j], s[j][a] - b[i][a]);
		if (gain[i][j]) opt[i][j] = {gain[i][j], di[i][j]};
	}
	for (int t = 1; t <= n; t++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (t != i && t != j && (!opt[i][j].second || (gain[i][t] + gain[t][j]) * opt[i][j].second > (di[i][t] + di[t][j]) * opt[i][j].first)) opt[i][j] = {gain[i][t] + gain[t][j], di[i][t] + di[t][j]};
	ll ans = 0;
	for (int i = 1; i <= n; i++) if (opt[i][i].second) ans = max(ans, opt[i][i].first / opt[i][i].second);
	cout << ans << '\n';
	return 0;
}

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