Submission #411682

#	Time	Username	Problem	Language	Result	Execution time	Memory
411682		sinamhdv	Travelling Merchant (APIO17_merchant)	C++11	45 / 100	99 ms	3096 KiB

merchant

// APIO17_merchant
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 120
#define MAXK 1020
#define MAXE 9950

int n, m, k;
int b[MAXN][MAXK], s[MAXN][MAXK];
int efrom[MAXE], eto[MAXE], ew[MAXE];
int dist[MAXN][MAXN];
int prof[MAXN][MAXN];
ll nd[MAXN][MAXN];

bool check(int x)
{
	FOR(i, 1, n + 1) FOR(j, 1, n + 1) nd[i][j] = x * (ll)dist[i][j] - prof[i][j];
	FOR(i, 1, n + 1) nd[i][i] = LINF;

	FOR(k, 1, n + 1) FOR(i, 1, n + 1) FOR(j, 1, n + 1) nd[i][j] = min(nd[i][j], nd[i][k] + nd[k][j]);
	FOR(i, 1, n + 1) if (nd[i][i] <= 0) return true;

	return false;
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m >> k;
	FOR(i, 1, n + 1) FOR(j, 0, k) cin >> b[i][j] >> s[i][j];

	FOR(i, 0, MAXN) fill(dist[i], dist[i] + MAXN, INF);
	FOR(i, 0, m) cin >> efrom[i] >> eto[i] >> ew[i], dist[efrom[i]][eto[i]] = ew[i];

	FOR(k, 1, n + 1) FOR(i, 1, n + 1) FOR(j, 1, n + 1) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

	FOR(i, 1, n + 1)
	{
		FOR(j, 1, n + 1)
		{
			if (dist[i][j] >= INF) continue;
			FOR(o, 0, k) if (s[j][o] > 0 && b[i][0] > 0)
				prof[i][j] = max(prof[i][j], s[j][o] - b[i][o]);
		}
	}

	int l = 0, r = INF;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (check(mid)) l = mid;
		else r = mid;
	}

	cout << l << endl;

	return 0;
}

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