Submission #107397

#	Time	Username	Problem	Language	Result	Execution time	Memory
107397		Noam527	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	129 ms	2228 KiB

merchant

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 1;
const int OOO = 1;
using namespace std;

int n, m, k;
ll B[101][1001], S[101][1001];
ll D[101][101] = {}, W[101][101];
ll d[101][101];
ll dist[101], cnt[101];

bool check(ll x) {
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
		d[i][j] = W[i][j] - x * D[i][j];

	for (int i = 0; i < n; i++) dist[i] = cnt[i] = 0;
	for (int iter = 0; iter <= n; iter++) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (i != j) {
					if (make_pair(dist[j], cnt[j]) < make_pair(dist[i] + d[i][j], cnt[i] + 1)) {
						if (iter == n) return true;
						dist[j] = dist[i] + d[i][j];
						cnt[j] = cnt[i] + 1;
					}
				}
			}
	}
	return false;
}

void preprocess() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (i != j) {
				for (int x = 0; x < k; x++)
					if (B[i][x] != -1 && S[j][x] != -1)
						W[i][j] = max(W[i][j], S[j][x] - B[i][x]);
			}
	for (int u = 0; u < n; u++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				D[i][j] = min(D[i][j], D[i][u] + D[u][j]);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++)
			cin >> B[i][j] >> S[i][j];
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		W[i][j] = 0;
		if (i != j) D[i][j] = inf;
	}
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		--u, --v;
		D[u][v] = w;
	}
	preprocess();

	ll lo = 0, hi = 1e9 + 3, mid;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (check(mid)) lo = mid;
		else hi = mid - 1;
	}
	finish(lo);
}

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