oj.uz

Submission #475336

# Submission time Handle Problem Language Result Execution time Memory
475336 2021-09-21T23:16:54 Z Hamed5001 Travelling Merchant (APIO17_merchant) C++14
0 / 100
 294 ms 2028 KB 
#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;
}

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 294 ms 2028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -