Submission #970632

#	Time	Username	Problem	Language	Result	Execution time	Memory
970632		MinaRagy06	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	240 ms	4444 KiB

merchant

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

const int N = 105, K = 1005;
const ll inf = 1e18;
array<ll, 2> a[N][K];
ll dist[N][N], dist2[N][N], dist3[N][N], c[N][N];
int n, m, t;
bool check(ll v) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist2[i][j] = -1e18;
			for (int k = 1; k <= n; k++) {
				if (dist[i][k] + dist3[k][j] <= inf / v) {
//					if (i == 1 && j == 1) {
//						cout << -(dist[i][k] + dist3[k][j]) * v + c[k][j] << ' ' << k << ' ' << c[k][j] << ' ' << dist[i][k] << ' ' << dist3[k][j] << '\n';
//					}
					dist2[i][j] = max(dist2[i][j], -(dist[i][k] + dist3[k][j]) * v + c[k][j]);
				}
			}
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist2[i][j] = max(dist2[i][j], dist2[i][k] + dist2[k][j]);
			}
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist2[i][k] + dist2[k][j] > dist2[i][j]) {
					dist2[i][j] = 1e18;
				}
			}
		}
	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= n; j++) {
//			cout << dist2[i][j] << ' ';
//		}
//		cout << '\n';
//	}
//	cout << dist[1][2] << ' ' << dist[3][1] << ' ' << dist2[2][3] << '\n';
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (dist[i][j] + dist[k][i] <= inf / v) {
					if (dist2[j][k] - (dist[i][j] + dist[k][i]) * v >= 0) {
//						cout << i << ' ' << j << ' ' << k << ' ' << i << ": " << dist2[j][k] << ' ' << dist[i][j] << ' ' << dist[k][i] << '\n';
						return 1;
					}
				}
			}
		}
	}
	return 0;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> t;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < t; j++) {
			cin >> a[i][j][0] >> a[i][j][1];
			if (a[i][j][0] == -1) {
				a[i][j][0] = 1e18;
			}
			if (a[i][j][1] == -1) {
				a[i][j][1] = -1e18;
			}
		}
	}
	memset(dist, '?', sizeof dist);
	memset(dist3, '?', sizeof dist3);
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		dist[u][v] = w;
		dist3[u][v] = w;
	}
	for (int i = 1; i <= n; i++) {
		dist[i][i] = 0;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				dist3[i][j] = min(dist3[i][j], dist3[i][k] + dist3[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			c[i][j] = -1e18;
			// buy at i, sell at j
			for (int k = 0; k < t; k++) {
//				if (i == 4 && j == 1) {
//					cout << - a[i][k][0] + a[j][k][1] << '\n';
//				}
				c[i][j] = max(c[i][j], - a[i][k][0] + a[j][k][1]);
			}
		}
	}
	ll l = 1, r = 1e18;
	while (l <= r) {
		ll md = ((l + r) >> 1);
		if (check(md)) {
			l = md + 1;
		} else {
			r = md - 1;
		}
	}
	cout << r << '\n';
	return 0;
}

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