Submission #475335

#	Time	Username	Problem	Language	Result	Execution time	Memory
475335		Hamed5001	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	319 ms	2080 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mxN = 110, mxK = 1010;
bool vis[mxN][mxK];
vector<pair<ll, ll>> adj[mxN];
vector<pair<ll, ll>> market[mxN];
ll N, M, K, ans;

void dfs(ll node, ll st, ll depth, ll pack, ll profit, ll time) {
	if (node == st && depth) {
		// cerr << profit << ' ' << time << endl;
	 return void(ans = max(ans, (ll)(profit/time)));
	}
	if (vis[node][pack+1])
		return;
	vis[node][pack+1] = 1;
	if (~pack && ~market[node][pack].second) {
		dfs(node, st, depth, -1, profit + market[node][pack].second, time);
	}
	if (!(~pack)) {
		for (auto& c : adj[node]) {
			for (ll i = 0; i < K; i++) {
				if (~market[node][i].first)
					dfs(c.first, st, depth+1, i, profit - market[node][i].first, time + c.second);	
			}
		}
	}
	for (auto& c : adj[node]) {
		dfs(c.first, st, depth+1, pack, profit, time + c.second);	
	}
}

void solve() {
	cin >> N >> M >> K;

	for (ll i = 1; i <= N; i++) {
		for (ll j = 0; j < K; j++) {
			ll b, s;
			cin >> b >> s;
			market[i].push_back({b, s});
		}
	}

	for (ll i = 0; i < M; i++) {
		ll u, v, t;
		cin >> u >> v >> t;
		adj[u].push_back({v, t});
	}


	for (ll i = 1; i <= N; i++) {
		memset(vis, 0, sizeof vis);
		dfs(i, i, 0, -1, 0, 0);
	}
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

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