Submission #1059173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059173		Onur_Ilgaz	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	26 ms	2140 KiB

merchant

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

int32_t main(){
	fast
	int n, m, K;
	cin >> n >> m >> K;
	vector <vector<int> > dist(n, vector <int> (n, inf));
	vector <vector<pair<int, int> > > opt(n, vector <pair<int, int> > (n));
	vector <vector<pair<int, int> > > price(n, vector <pair<int, int> > (K));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < K; j++) {
			int a, b;
			cin >> a >> b;
			price[i][j] = {a, b};
		}
	}
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		a--, b--;
		dist[a][b] = min(dist[a][b], w);
	}
	for(int k = 0; k < n; k++) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	auto maxi = [](pair<int, int> a, pair<int, int> b) {
		__int128__ aa = a.first * b.second, bb = b.first * a.second;
		if(aa > bb) {
			return a;
		}
		else if(aa == bb) {
			return min(a, b);
		}
		return b;
	};
	auto add = [](pair<int, int> a, pair<int, int> b) {
		return make_pair(a.first + b.first, a.second + b.second);
	};
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			opt[i][j].second = dist[i][j];
			for(int item = 0; item < K; item++) {
				int sell = price[j][item].second, buy = price[i][item].first;
				if(~sell and ~buy) {
					opt[i][j] = maxi(opt[i][j], {sell - buy, dist[i][j]});
				}
			}
		}
	}
	for(int k = 0; k < n; k++) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				opt[i][j] = maxi(opt[i][j], add(opt[i][k], opt[k][j]));
			}
		}
		// for(int i = 0; i < n; i++) {
		// 	for(int j = 0; j < n; j++) {
		// 		cout << opt[i][j].first % inf << " ";
		// 	}
		// 	cout << "\n";
		// }
		// cout << "\n";
		// for(int i = 0; i < n; i++) {
		// 	for(int j = 0; j < n; j++) {
		// 		cout << opt[i][j].second % inf << " ";
		// 	}
		// 	cout << "\n";
		// }
		// cout << "---------------------\n";
	}
	pair<int, int> ans = {0, 1};
	for(int st = 0; st < n; st++) {
		if(dist[st][st] == inf) continue;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				// if(i == j) continue;
				auto go = opt[st][i], come = opt[j][st];
				if(i == st) go = {0, 0};
				if(j == st) come = {0, 0};
				// cout << add(add(go, come), opt[i][j]).first << " " << add(add(go, come), opt[i][j]).second << "\n";
				ans = maxi(ans, add(add(go, come), opt[i][j]));
			}
		}
		// cout << ans.first << " " << ans.second << "\n\n";
	}
	cout << ans.first / ans.second << "\n";
}

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