APIO 2017 - Traveling Merchant

First, find the maximum profit of each footpath by comparing the buying and selling prices of the endpoints for each of the $K$ items. We now have a directed graph where each edge has a profit $p$ and a time to traverse $t$.

Ratios are inconvenient, so let's consider a simpler problem: given $R$, can we find a profit cycle with profit $P$ and time $T$ such that $P/T\ge R$?

This is convenient because we can make it linear: this problem is equivalent to checking whether we can find a profit cycle with profit $P$ and time $T$ such that $P-TR\ge 0$. If we weight each edge as $p-tR$, this is equivalent to checking whether a non-negative cycle exists in the graph.

Since $R$ is good if $R+1$ is good, we can binary search for the largest good $R$. We can then use Floyd-Warshall to check whether there is a negative cycle.

(For a similar problem, see Cruise from BkOI 2016. Beware though - it's geometry!)

Code

1#include <bits/stdc++.h>
2#define FOR(i, x, y) for (int i = x; i < y; i++)
3typedef long long ll;
4using namespace std;
5
6const ll INF = LLONG_MAX / 2;
7
8int n, m, x;
9ll b[101][1001], s[101][1001];
10ll graph[101][101], profit[101][101], graph2[101][101];