oj.uz

Submission #474005

# Submission time Handle Problem Language Result Execution time Memory
474005 2021-09-16T15:25:54 Z Hamed5001 Travelling Merchant (APIO17_merchant) C++14
0 / 100
 116 ms 708 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mxN = 101;
ll N, M, K;
pair<ll, ll> MARKET[mxN][mxN];
bool vis[mxN+50][mxN+50];
vector<pair<ll, pair<ll, ll>>> adj[mxN];

ll ans = 0;

void dfs(ll node, ll st, ll t, ll profit, ll holding) {
	if (node == st && t) {
		if (!holding) {
			ans = max(ans, (ll)floor(profit/t));
		}
		return;
	}
	if (holding && ~MARKET[node][holding].second) {
		vis[node][0] = 1;
		dfs(node, st, t, profit + MARKET[node][holding].second, 0);
	}
	for (auto c : adj[node]) {
		if (!vis[c.first][holding]) {
			vis[c.first][holding] = 1;
			dfs(c.second.first, st, t + c.second.second, profit, holding);
		}
		if (!holding) {
			for (int i = 1; i <= K; i++) {
				if (~MARKET[node][i].first && !vis[c.first][i]) {
					vis[c.first][i] = 1;
					dfs(c.second.first, st, t + c.second.second, profit - MARKET[node][i].first, i);
				}
			}
		}
	}
}

void solve() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> MARKET[i][j].first >> MARKET[i][j].second;
		}
	}

	for (int i = 0; i < M; i++) {
		int U, V, T;
		cin >> U >> V >> T;
		adj[U].push_back({i, {V, T}});
	}

	for (int i = 1; i <= N; i++) {
		memset(vis, 0, sizeof vis);
		dfs(i, i, 0, 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 Runtime error 19 ms 708 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 460 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 332 KB Output isn't correct
2 Halted 0 ms 0 KB -