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 \geq 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 \geq 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!)

Implementation

Copy
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const ll INF = LLONG_MAX / 2;

int n, m, x;
ll b[101][1001], s[101][1001];
ll graph[101][101], profit[101][101], graph2[101][101];