Submission #1171512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171512		tkm_algorithms	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	57 ms	2120 KiB

merchant

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
	
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
 
const char nl = '\n';
const int N = 105;
const int K = 1005;
const int inf = 1e10;

int n, m, k;
int b[N][K], s[N][K];
int g[N][N], profit[N][N], g2[N][N];

void init() {
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= n; ++j)g[i][j] = inf;
}

void build(int adj[N][N]) {
	for (int k2 = 1; k2 <= n; ++k2)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				adj[i][j] = min(adj[i][j], adj[i][k2]+adj[k2][j]);	
}

bool check(int mid) {
	for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j) {
				g2[i][j] = min(g[i][j], inf/mid)*mid-profit[i][j];
			}
	build(g2);
	for (int i = 1; i <= n; ++i)
		if (g2[i][i] <= 0)return true;
	return false;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> k;
    
    for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= k; ++j)cin >> b[i][j] >> s[i][j];
	}
	
	init();
	for (int i = 0; i < m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		g[u][v] = min(g[u][v], w);
	}
	
	build(g);
	
	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j <= n; ++j)
			for (int k2 = 1; k2 <= k; ++k2)
				if (s[j][k2] != -1 && b[i][k2] != -1)
					profit[i][j] = max(profit[i][j], s[j][k2]-b[i][k2]);
	
	int l = 1, r = 1e9;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid))l = mid+1;
		else r = mid-1;
	}
	cout << r;
	return 0;
}

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