Submission #118940

#	Time	Username	Problem	Language	Result	Execution time	Memory
118940		Mahdi_Jfri	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	92 ms	3448 KiB

merchant

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e2 + 20;
const int maxm = 1e4 + 20;
const int maxk = 1e3 + 20;

int b[maxn][maxk] , s[maxn][maxk];

int d[maxn][maxn] , best[maxn][maxn] , n;

ll res[maxn][maxn];

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

	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(i != j)
					res[i][j] = min(res[i][j] , res[i][k] + res[k][j]);

	for(int i = 0; i < n; i++)
		for(int j = i + 1; j < n; j++)
			if(res[i][j] + res[j][i] <= 0)
					return 1;

	return 0;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int m , k;
	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];

	memset(d , 63 , sizeof d);
	for(int i = 0; i < m; i++)
	{
		int a , b , c;
		cin >> a >> b >> c;
		a-- , b--;

		d[a][b] = min(d[a][b] , c);
	}

	for(int i = 0; i < n; i++)
		d[i][i] = 0;

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

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			for(int ind = 0; ind < k; ind++)
				if(b[i][ind] != -1 && s[j][ind] != -1)
					best[i][j] = max(best[i][j] , s[j][ind] - b[i][ind]);

	int l = 0 , r = 2e9;

	while(r - l > 1)
	{
		int m = (l + r) / 2;
		if(check(m))
			l = m;
		else
			r = m;
	}

	cout << l << endl;
}

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