Submission #1209582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209582		k1r1t0	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	85 ms	2628 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 110;
const int K = 1100;
const int INF = (int)(2e18);

int n, m, k, b[N][K], s[N][K], p[N][N], d[N][N];
vector<array<int, 3>> edge;

bool solve(int t) {
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
		d[i][j] = INF;
	for (auto [u, v, w] : edge)
		d[u][v] = min(d[u][v], w * t);
	for (int k = 1; k <= n; k++)
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
		if (d[i][k] < INF && d[k][j] < INF)
			d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
		if (d[i][j] < INF)
			d[i][j] -= p[i][j];
	for (int k = 1; k <= n; k++)
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
		if (d[i][k] < INF && d[k][j] < INF)
			d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	for (int i = 1; i <= n; i++)
		if (d[i][i] <= 0)
			return true;
	return false;
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= k; j++)
		cin >> b[i][j] >> s[i][j];
	for (int i = 1; i <= m; i++) {
		int u, v, w; cin >> u >> v >> w;
		edge.push_back({u, v, w});
	}
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++) {
		p[i][j] = 0;
		for (int t = 1; t <= k; t++)
			if (s[j][t] != -1 && b[i][t] != -1)
				p[i][j] = max(p[i][j], s[j][t] - b[i][t]);
	}
	int l = 0, r = (int)(1e9);
	while (l < r) {
		int mid = (l + r) / 2;
		if (solve(mid + 1)) l = mid + 1;
		else r = mid;
	}
	cout << l;
}

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