Submission #1059085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059085		pawned	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	109 ms	4488 KiB

merchant

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

int N, M, K;

vector<vi> opt(vector<vi> adj) {	// adjacency matrix of distance, optimize
	vector<vi> res = adj;
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				res[i][j] = min(res[i][j], res[i][k] + res[k][j]);
			}
		}
	}
	return res;
}

int main() {
	fastIO();
	cin>>N>>M>>K;
	vector<vi> buy(N, vi(K, -1));	// buying price, higher
	vector<vi> sell(N, vi(K, -1));	// selling price, lower
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K; j++) {
			cin>>buy[i][j]>>sell[i][j];
		}
	}
	vector<vi> adj(N, vi(N, 1e18));
	for (int i = 0; i < M; i++) {
		int u, v; ll w;
		cin>>u>>v>>w;
		u--; v--;
		adj[u][v] = w;
	}
	adj = opt(adj);
/*	cout<<"adj: "<<endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout<<adj[i][j]<<" ";
		}
		cout<<endl;
	}*/
	vector<vi> profit(N, vi(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < K; k++) {
				if (sell[j][k] != -1 && buy[i][k] != -1)
					profit[i][j] = max(profit[i][j], sell[j][k] - buy[i][k]);
			}
		}
	}
/*	cout<<"profit: "<<endl;
	for (vi v : profit) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	ll low = 1;
	ll high = 1e18;
	ll ans = 0;
	// maximum k so has nonpos cyc where each edge as k * dist - profit
	// "nonpositive loss", paid per time
	while (low <= high) {	// true, true, true, false, false, false
		ll mid = (low + high) / 2;
		vector<vi> adjc(N, vi(N, 0));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				adjc[i][j] = mid * min(adj[i][j], (ll)(2e18) / mid) - profit[i][j];
			}
		}
/*		cout<<"adjc before: "<<endl;
		for (vi v : adjc) {
			for (ll x : v)
				cout<<x<<" ";
			cout<<endl;
		}*/
		adjc = opt(adjc);
/*		cout<<"adjc after: "<<endl;
		for (vi v : adjc) {
			for (ll x : v)
				cout<<x<<" ";
			cout<<endl;
		}*/
		// if any node to itself is <= 0, then works
		bool works = false;
		for (int i = 0; i < N; i++) {
			if (adjc[i][i] <= 0)
				works = true;
		}
		if (works) {
			ans = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
//	cout<<"ANSWER: ";
	cout<<ans<<endl;
}

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