Submission #732357

#	Time	Username	Problem	Language	Result	Execution time	Memory
732357		SanguineChameleon	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	490 ms	1400 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxN = 1e2 + 20;
const int maxK = 1e3 + 20;
const int inf1 = 1e9 + 20;
const long long inf2 = 1e18L + 20;
int buy[maxN][maxK];
int sell[maxN][maxK];
int dist[maxN][maxN];
int prof[maxN][maxN];
long double cost[maxN][maxN];
long double dist2[maxN];
int N, M, K;

bool check() {
	for (int i = 1; i <= N; i++) {
		dist2[i] = 0.0L;
	}
	for (int iter = 0; iter < N; iter++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dist2[j] < dist2[i] + cost[i][j]) {
					if (iter == N - 1) {
						return true;
					}
					dist2[j] = dist2[i] + cost[i][j];
				}
			}
		}
	}
	return false;
}

void just_do_it() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) {
				dist[i][j] = 0;
			}
			else {
				dist[i][j] = inf1;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> buy[i][j] >> sell[i][j];
		}
	}
	for (int i = 1; i <= M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		dist[u][v] = min(dist[u][v], w);
	}
	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++) {
			prof[i][j] = 0;
			for (int k = 1; k <= K; k++) {
				if (buy[i][k] != -1 && sell[j][k] != -1) {
					prof[i][j] = max(prof[i][j], sell[j][k] - buy[i][k]);
				}
			}
		}
	}
	long double res = 0;
	long double lt = 1;
	long double rt = inf1;
	for (int iter = 0; iter < 100; iter++) {
		long double mt = (lt + rt) / 2;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dist[i][j] == inf1) {
					cost[i][j] = -inf2;
				}
				else {
					cost[i][j] = 1LL * prof[i][j] - 1LL * dist[i][j] * mt; 
				}
			}
		}
		if (check()) {
			res = mt;
			lt = mt;
		}
		else {
			rt = mt;
		}
	}
	cout << (int)(trunc(res));
}

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