Submission #1260138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260138		kamrad	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1097 ms	21312 KiB

merchant

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

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using ll  = long long;
using ld  = long double;
using pii = pair<ll, ll>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, ll>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define rand(l, r)        uniform_ll_distribution<ll64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const ll Mod    = 1e9 + 7; //998244353;
const ll LG     = 64;
const ll SQ     = 500;
const ll Inf    = 2e15 + 10;
const ll maxN   = 1e2 + 10;
const ll maxK   = 1e3 + 10;

ll n, m, k;

ll b[maxN][maxK];
ll s[maxN][maxK];
ll p[maxN][maxN];
ll e[maxN][maxN][maxN];
ll dist[maxN][maxN][maxN];

bool check(ll x) {
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			e[i][j][0] = x*dist[i][j][n]-p[i][j];
	for(int i = 1; i <= n; i++)
		e[i][i][0] = Inf;

	for(int x = 1; x <= n; x++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				e[i][j][x] = min(e[i][j][x-1], e[i][x][x-1]+e[x][j][x-1]);
	for(int i = 1; i <= n; i++)
		if(e[i][i][n] <= 0)
			return true;
	return false;
}

int main() {
	IOS;
	
	cin >> n >> m >> k;
		
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= k; j++)
			cin >> b[i][j] >> s[i][j];

	for(ll i = 0; i < maxN; i++)
		for(ll j = 0; j < maxN; j++)
			for(ll x = 0; x < maxN; x++)
				dist[i][j][x] = Inf;

	for(ll i = 1; i <= m; i++) {
		ll u, v, t;
		cin >> u >> v >> t;
		minr(dist[u][v][0], t);
	}
	for(ll i = 1; i <= n; i++)
		dist[i][i][0] = 0;

	for(ll x = 1; x <= n; x++)
		for(ll i = 1; i <= n; i++)
			for(ll j = 1; j <= n; j++)
				dist[i][j][x] = min(dist[i][j][x-1], dist[i][x][x-1]+dist[x][j][x-1]);

	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= n; j++)
			for(ll x = 1; x <= k; x++)
				if(b[i][x] != -1 and s[j][x] != -1)
					maxr(p[i][j], s[j][x]-b[i][x]);

	ll ans = -Inf;
	for(int i = 2; i <= n; i++)
		maxr(ans, p[1][i]/(dist[1][i][n]+dist[i][1][n]));
	if(ans == -Inf)
		ans = 0;
	for(ll i = 1; i <= ans; i++)
		if(!check(i)) {
			cout << -1;
			return 0;
		}
	cout << ans;
	return 0;
//	for(ll i = 1; i <= n; i++)
//		p[i][i] = -Inf;

	ll l = 0;
	ll r = 1e18;
	while(l+1 < r) {
		ll mid = (l+r)>>1;
		if(check(mid))
			l = mid;
		else
			r = mid;
	}
	cout << l;
}

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