Submission #466340

#	Time	Username	Problem	Language	Result	Execution time	Memory
466340		nonsensenonsense1	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	59 ms	2240 KiB

merchant

#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>

const int N = 100;
const int K = 1000;

int n, m, k, dist[N][N], val[N][N], b[N][K][2];
long long to[N];
bool prev[N], cur[N];

bool test(int x) 
{
	memset(to, 0xcf, N << 3);
	memset(cur, 0, N);
	cur[0] = 1;
	for (int i = 0; i <= n; ++i) {
		std::swap(cur, prev);
		memset(cur, 0, N);
		for (int j = 0; j < n; ++j) if (prev[j]) for (int k = 0; k < n; ++k) {
			long long d = to[j] + val[j][k] - (long long)dist[j][k] * x;
			if (d >= to[k]) {
				cur[k] = true;
				to[k] = d;
			}
		}
	}
	for (int i = 0; i < 2 * n; ++i) if (cur[i]) return true;
	return false;
}

int main() 
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; ++i) for (int j = 0; j < k; ++j) scanf("%d%d", b[i][j], b[i][j] + 1);
	memset(*dist, 0x3f, N * N << 2);
	for (int i = 0; i < m; ++i) {
		int v, w, t;
		scanf("%d%d%d", &v, &w, &t);
		dist[v - 1][w - 1] = t;
	}
	for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) dist[j][k] = std::min(dist[j][k], dist[j][i] + dist[i][k]);
	for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) for (int l = 0; l < k; ++l) if (b[i][l][0] != -1 && b[j][l][1] != -1) val[i][j] = std::max(val[i][j], b[j][l][1] - b[i][l][0]);
	int l = 0, r = 1000000000, ans = -1;
	while (l <= r) {
		int m = l + r >> 1;
		if (test(m)) {
			ans = m;
			l = m + 1;
		}
		else r = m - 1;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int m = l + r >> 1;
      |           ~~^~~
merchant.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:36:63: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  for (int i = 0; i < n; ++i) for (int j = 0; j < k; ++j) scanf("%d%d", b[i][j], b[i][j] + 1);
      |                                                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d%d%d", &v, &w, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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