Submission #945249

#	Time	Username	Problem	Language	Result	Execution time	Memory
945249		TAhmed33	Travelling Merchant (APIO17_merchant)	C++98	0 / 100	39 ms	2392 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e16;
const int MAXN = 1e3 + 25;
vector <int> adj[MAXN];
vector <ll> dd[MAXN];
int n, m, k;
ll get () {
	bool vis[n + 1];
	queue <int> cur; cur.push(1); memset(vis, false, sizeof(vis));
	ll dist[n + 1] = {}; vis[1] = 1;
	while (!cur.empty()) {
		int l = cur.front(); cur.pop();
		for (auto j : adj[l]) {
			if (!vis[j]) {
				vis[j] = 1; dist[j] = dist[l] + 1;
				cur.push(j);
			}
		}
	}
	ll tot = inf;
	for (int j = 1; j <= n; j++) {
		if (!vis[j]) continue;
		for (auto k : adj[j]) {
			if (dist[j] == dist[k]) tot = min(tot, 2 * dist[j] + 1);
		}
	}
	for (int j = 1; j <= n; j++) {
		if (!vis[j]) continue;
		int s = 0;
		for (auto k : adj[j]) {
			if (k == 1) continue;
			if (dist[k] == dist[j] - 1) s++;
		}
		if (s > 1) tot = min(tot, 2 * (dist[j] - 1) + 2);
	}
	return tot == inf ? -1 : tot;
}
int main () {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		dd[i].resize(k);
		for (auto &j : dd[i]) {
			ll x, y; cin >> x >> y;
			j = y - x;
		}
	}
	sort(dd[1].begin(), dd[1].end());
	ll x = get();
	if (x == -1) {
		cout << "0\n";
		return 0;
	}
	reverse(dd[1].begin(), dd[1].end());
	ll mx = 0, sum = 0;
	for (int i = 0; i < (int)dd[1].size(); i++) {
		sum += dd[1][i];
		mx = max(mx, sum / (x * (i + 1)));
	}
	cout << mx << '\n';
}

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