Submission #497177

#	Time	Username	Problem	Language	Result	Execution time	Memory
497177		Sohsoh84	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	118 ms	39644 KiB

merchant

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 3000 + 10;
const ll MAXK = 1000 + 10;
const ll INF = 1e9 + 10; // ?

ll n, m, tk, B[MAXN][MAXK], S[MAXN][MAXK], max_prof[MAXN][MAXN], tdist[MAXN][MAXN];
int dist[MAXN][MAXN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for (int i = 0; i < MAXN; i++) {
		memset(dist[i], 63, sizeof dist[i]);
		dist[i][i] = 0;
	}

	cin >> n >> m >> tk;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= tk; j++) cin >> B[i][j] >> S[i][j];

	for (int i = 1; i <= m; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		dist[u][v] = min(dist[u][v], d);
	}

	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]);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int t = 1; t <= tk; t++)
				if (S[j][t] >= 0 && B[i][t] >= 0)
					max_prof[i][j] = max(max_prof[i][j], S[j][t] - B[i][t]);
		}
	}
	

	ll l = 0, r = ll(2e9) + 10;
	while (l < r) {
		ll mid = (l + r + 1) >> 1;	
		
		bool flag = false;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				tdist[i][j] = dist[i][j] * mid - max_prof[i][j];

		for (int k = 1; k <= n; k++)
			for (int v = 1; v <= n; v++)
				for (int u = 1; u <= n; u++)
					if (u != v) 
						tdist[v][u] = min(tdist[v][u], tdist[v][k] + tdist[k][u]);

		// loops
		for (int v = 1; v <= n; v++)
			for (int u = 1; u <= n; u++)
				if (v != u)
					flag |= (tdist[v][u] + tdist[u][v] <= 0);

		if (flag) l = mid;
		else r = mid - 1;
	}

	cout << l << endl;
	return 0;
}

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