Submission #347750

#	Time	Username	Problem	Language	Result	Execution time	Memory
347750		toshtosh	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	45 ms	3436 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ll n, m, k, ans = 0;
	scanf("%lld %lld %lld", &n, &m, &k);
	ll b[n][k], s[n][k], x, y, z, a[n][n], d[n][n], p[n][n], q[n][n];
	for (ll i = 0; i < n; i++){
		for (ll j = 0; j < n; j++){
			a[i][j] = 0, d[i][j] = 1000000000;
		}
	}
	for (ll i = 0; i < n; i++){
		for (ll j = 0; j < k; j++) scanf("%lld %lld", &b[i][j], &s[i][j]);
		for (ll j = 0; j < i; j++){
			for (ll l = 0; l < k; l++){
				if (s[j][l] != -1 && b[i][l] != -1) a[i][j] = max(a[i][j], s[j][l] - b[i][l]);
				if (s[i][l] != -1 && b[j][l] != -1) a[j][i] = max(a[j][i], s[i][l] - b[j][l]);
			}
		}
	}
	for (ll i = 0; i < m; i++){
		scanf("%lld %lld %lld", &x, &y, &z), x--, y--;
		d[x][y] = z;
	}
	for (ll i = 0; i < n; i++){
		for (ll j = 0; j < n; j++){
			for (ll l = 0; l < n; l++){
				d[j][l] = min(d[j][l], d[j][i] + d[i][l]);
			}
		}
	}
	for (ll i = 0; i < n; i++){
		for (ll j = 0; j < n; j++){
			p[i][j] = a[i][j], q[i][j] = d[i][j];
		}
	}
	for (ll i = 0; i < n; i++){
		for (ll j = 0; j < n; j++){
			for (ll l = 0; l < n; l++){
				if (j == i || l == i) continue;
				ans = max(ans, (a[i][j] + p[j][l] + a[l][i]) / (d[i][j] + q[j][l] + d[l][i]));
			}
		}
		for (ll j = 0; j < n; j++){
			for (ll l = 0; l < n; l++){
				if (p[j][l] * (q[j][i] + q[i][l]) < (p[j][i] + p[i][l]) * q[j][l]){
					p[j][l] = p[j][i] + p[i][l], q[j][l] = q[j][i] + q[i][l];
				}
			}
		}
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:6:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    6 |  scanf("%lld %lld %lld", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:14:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |   for (ll j = 0; j < k; j++) scanf("%lld %lld", &b[i][j], &s[i][j]);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |   scanf("%lld %lld %lld", &x, &y, &z), x--, y--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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