Submission #347606

#	Time	Username	Problem	Language	Result	Execution time	Memory
347606		nicholask	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	64 ms	3180 KiB

merchant

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int b[101][1001],s[101][1001];
int g[101][101],floyd[101][101];
signed main(){
	cin>>n>>m>>k;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=k; j++) cin>>b[i][j]>>s[i][j];
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++) g[i][j]=floyd[i][j]=1e18;
	}
	for (int i=0; i<m; i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u][v]=min(g[u][v],w);
		floyd[u][v]=min(floyd[u][v],w);
	}
	for (int l=1; l<=n; l++){
		for (int i=1; i<=n; i++){
			for (int j=1; j<=n; j++) floyd[i][j]=min(floyd[i][j],floyd[i][l]+floyd[l][j]);
		}
	}
	int ans=0;
	for (int i=1; i<=n; i++){
		if (floyd[1][i]==1e18||floyd[i][1]==1e18) continue;
		for (int j=1; j<=k; j++) ans=max(ans,(s[i][j]-b[1][j])/(floyd[1][i]+floyd[i][1]));
	}
	cout<<ans<<endl;
}

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