Submission #1088455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088455		4QT0R	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	121 ms	5968 KiB

merchant

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

ll buy[102][1003];
ll sell[102][1003];

ll adj[102][102];
ll oo=1e18;

ll val[102][102];

ll dp[102][102];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,m,k;
	cin >> n >> m >> k;
	for (int i = 1; i<=n; i++)fill(adj[i]+1,adj[i]+n+1,oo);
	for (int i = 1; i<=n; i++)for (int j = 1; j<=k; j++){
		int a,b;
		cin >> a >> b;
		buy[i][j]=a;
		sell[i][j]=b;
	}
	for (int i = 1,a,b,c; i<=m; i++){
		cin >> a >> b >> c;
		adj[a][b]=c;
	}
	for (int i = 1; i<=n; i++)adj[i][i]=0;
	for (int a = 1; a<=n; a++){
		for (int v = 1; v<=n; v++){
			for (int u = 1; u<=n; u++){
				if (adj[v][a]==oo || adj[a][u]==oo)continue;
				adj[v][u]=min({adj[v][u],oo,adj[v][a]+adj[a][u]});
			}
		}
	}
	for (int v = 1; v<=n; v++){
		for (int u = 1; u<=n; u++){
			for (int i = 1; i<=k; i++)if (buy[v][i]!=-1 && sell[u][i]!=-1){
				val[v][u]=max(val[v][u],sell[u][i]-buy[v][i]);
			}
		}
	}
	ll l=0,p=1e9,md;
	while(l<p){
		ll md=(l+p+1)/2;
		for (int i = 1; i<=n; i++)for (int j = 1; j<=n; j++){
			if (adj[i][j]==oo)dp[i][j]=oo;
			else dp[i][j]=md*adj[i][j]-val[i][j];
		}
		for (int a = 1; a<=n; a++){
			for (int v = 1; v<=n; v++){
				for (int u = 1; u<=n; u++){
					if (adj[v][a]==oo || adj[a][u]==oo)continue;
					dp[v][u]=max(min(dp[v][u],dp[v][a]+dp[a][u]),-oo);
				}
			}
		}
		bool ok=false;
		for (int v = 1; v<=n; v++)for (int u = 1; u<=n; u++){
			if (adj[v][u]==oo || adj[u][v]==oo || u==v)continue;
			if (dp[v][u]+dp[u][v]<=0)ok=true;
		}
		if (ok)l=md;
		else p=md-1;
	}
	cout << (int)l << '\n';
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:48:15: warning: unused variable 'md' [-Wunused-variable]
   48 |  ll l=0,p=1e9,md;
      |               ^~

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