Submission #821287

#	Time	Username	Problem	Language	Result	Execution time	Memory
821287		Alan	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	83 ms	3156 KiB

merchant

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

ll di[105][105], b[105][1005], s[105][1005];
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];
			if (b[i][j] == -1) b[i][j] = inf;
		}
		for (int j = 1; j <= k; j++) {
			cin >> s[i][j];
			if (s[i][j] == -1) s[i][j] = -inf;
		}
	}
	while (m--) {
		int u, v;
		ll t;
		cin >> u >> v >> t;
		di[u][v] = min(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]);
	ll ans = 0;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int t = 1; t <= k; t++) ans = max(ans, (s[j][t] - b[i][t]) / (di[i][j] + di[j][i]));
	cout << ans << '\n';
	return 0;
}

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