Submission #405477

#	Time	Username	Problem	Language	Result	Execution time	Memory
405477		ritul_kr_singh	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	87 ms	4184 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int INF = 2e9;

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, k, u, v; cin >> n >> m >> k;
	int b[n][k], s[n][k], ok = 1;
	for(int i=0; i<n; ++i){
		for(int j=0; j<k; ++j){
			cin >> b[i][j] >> s[i][j];
			if(b[i][j] < 0) b[i][j] = INF;
			if(s[i][j] < 0) s[i][j] = -INF;
		}
	}

	int d[n][n], p[n][n];
	for(int i=0; i<n; ++i) fill(d[i], d[i]+n, INF), fill(p[i], p[i]+n, 0LL);

	while(m--) cin >> u >> v >> d[u-1][v-1];

	for(int l=0; l<n; ++l)
		for(int i=0; i<n; ++i)
			for(int j=0; j<n; ++j)
				d[i][j] = min(d[i][j], d[i][l] + d[l][j]);

	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			for(int l=0; l<k; ++l)
				p[i][j] = max(p[i][j], (b[i][l] < 0 or s[j][l] < 0) ? 0LL : s[j][l]-b[i][l]);

	int low = 0, high = 1e9;
	while(low < high){
		int x = (low + high + 1) / 2LL;

		int dp[n][n];
		for(int i=0; i<n; ++i)
			for(int j=0; j<n; ++j)
				dp[i][j] = p[i][j] - x * d[i][j];
		for(int l=0; l<n; ++l)
			for(int i=0; i<n; ++i)
				for(int j=0; j<n; ++j)
					dp[i][j] = max(dp[i][j], dp[i][l] + dp[l][j]);

		bool ok = 0;
		for(int i=0; i<n; ++i)
			if(dp[i][i] >= 0) ok = 1;

		if(ok) low = x;
		else high = x - 1;
	}

	cout << (ok ? low : 0LL);
}

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