Submission #977046

#	Time	Username	Problem	Language	Result	Execution time	Memory
977046		Halym2007	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	1069 ms	2128 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair <ll, ll>
#define ff first
#define ss second
#define sz size()

const int N = 1e2 + 5;
const int K = 1e3 + 5;
ll baha[N], vis[N], buy[N][K], sell[N][K], n, m, d, dis[N][N], profit[N][N];
vector <ll> nodes;
vector <pii> v[N];
ll node, val, new_jog;

ll ugrat () {
	ll ret = 0;
	for (int i = 1; i < (int)nodes.sz; ++i) {
		for (int j = 0; j < i; ++j) {
			ll x = nodes[j], y = nodes[i];
			baha[i] = max (baha[i], baha[j] + profit[x][y]);
		}
		ret = max (ret, baha[i]);
	}
	for (int i = 0; i < (int)nodes.sz; ++i) {
		baha[i] = 0;
	}
	return ret;
 }

void dfs (ll x, ll wagt) {
	if (vis[x]) {
		if (x == node) {
			nodes.pb(x);
//			for (int i : nodes) {
//				cout << i << " ";
//			}
//			exit(0);
			ll jog = ugrat ();
			jog -= (val * 1LL * wagt);	
			if (jog >= 0) new_jog = 1;
			nodes.pop_back();
		}
		return;
	}
	vis[x] = 1;
	nodes.pb (x);
	for (pii i : v[x]) {
		dfs (i.ff, wagt + (ll)i.ss);
	}
	vis[x] = 0;
	nodes.pop_back();
}


bool check (ll x) {
	// jog - x * time >= 0
	for (ll i = 1; i <= n; ++i) {
		node = i;val = x;
		new_jog = 0;
		dfs (node, 0);
		if (new_jog) return 1;
	}
	return 0;
}



int main () {
//	freopen ("input.txt", "r", stdin);
	cin >> n >> m >> d;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= d; ++j) {
			cin >> buy[i][j] >> sell[i][j];
		}
	}
//	if (sana == 1) {
//		cout << "1\n";
//		return 0;
//	}
	for (int i = 1; i <= m; ++i) {
		ll l, r, w;
		cin >> l >> r >> w;
		v[l].pb ({r, w});
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (i == j) continue;
			for (int k = 1; k <= d; ++k) {
				// k-th item-y i-njiden satyn alyan j-nynjyda satyan
				if (sell[j][k] != -1 and buy[i][k] != -1) 
				profit[i][j] = max (profit[i][j], sell[j][k] - buy[i][k]);
			}
		}
	}
//	cout << profit[1][2];
//	return 0;
	ll l = 0, r = 1e9 + 5, jog = 0;
	int sana = 0;
	while (l <= r) {
		ll md = (l + r) / 2;
		++sana;
//		if (sana == 1) {
//			cout << "1\n";
//			return 0;
//		}
		if (check (md)) {
			jog = md;
			l = md + 1;
		}
		else {
			r = md - 1;
		}
	} 
	cout << jog;
}

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