Submission #84245

#	Time	Username	Problem	Language	Result	Execution time	Memory
84245		shoemakerjo	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	38 ms	3452 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define maxn 101
#define maxk 1010
int N, M, K;
const ll inf = 1LL << 61;

ll dist[maxn][maxn];
ll buy[maxn][maxk];
ll sell[maxn][maxk];
pll prof[maxn][maxn];

bool isless(pll u, pll v) {
	if (u.first == 0 && u.second == 0) return true;
	return u.first*1.0/u.second < v.first*1.0/v.second;

}
bool isgreater(pll u, pll v) {
	return u.first*1.0/u.second > v.first*1.0/v.second;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dist[i][j] = inf;
		}
		dist[i][i] = inf;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> buy[i][j] >> sell[i][j];
		}
	}
	int vp, wp; ll tp;
	for (int i = 0; i < M; i++) {
		cin >> vp >> wp >> tp;
		dist[vp][wp] = min(dist[vp][wp], tp);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				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++) {
			prof[i][j] = pll(0, dist[i][j]);
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			for (int k = 1; k <= K; k++) {
				if (buy[i][k] == -1 || sell[j][k] == -1) continue;

				pll cur = pll(0-buy[i][k]+sell[j][k], dist[i][j]);
				if (isgreater(cur, prof[i][j])) {
					prof[i][j] = cur;
					
				}
			}
		}
	}


	

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {

			// if (i == j) continue;


			for (int k = 1; k <= N; k++) {
				pll cur = pll(prof[i][k].first + prof[k][j].first,
					prof[i][k].second + prof[k][j].second);
				if (isgreater(cur, prof[i][j])) {
					prof[i][j] = cur;
				}
			}
		}
	}
	

	ll ans = 0LL;
	for (int i = 1; i <= N; i++) {
		ans = max(ans, prof[i][i].first/prof[i][i].second);
	}
	// for (int i = 1; i <= N; i++) {
	// 	for  (int j = 1; j <= N; j++) {
	// 		if (i == j) continue;

	// 		// cout << "dist from " << i << " to " << j << " is " << dist[i][j] << endl;
	// 		// cout << i << " to " << j << " gets me a profit of " << 
	// 		// 	prof[i][j].first << " div " << prof[i][j].second << endl;

	// 		ll topg = prof[i][j].first + prof[j][i].first;
	// 		ll botg = prof[i][j].second + prof[j][i].second;

	// 		// cout << "      " << i << " through " << j << " is " << topg << " div " << botg << endl;

	// 		ans = max(ans, topg/botg);
	// 	}
	// }
	cout << ans << endl;

}

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