Submission #475334

#	Time	Username	Problem	Language	Result	Execution time	Memory
475334		Hamed5001	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	297 ms	2484 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

void dfs(int node, int st, int depth, int pack, int profit, int time) {
	if (node == st && depth) {
		// cerr << profit << ' ' << time << endl;
	 return void(ans = max(ans, (int)(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 (int 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 (int i = 1; i <= N; i++) {
		for (int j = 0; j < K; j++) {
			int b, s;
			cin >> b >> s;
			market[i].push_back({b, s});
		}
	}

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


	for (int 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