Submission #743778

#	Time	Username	Problem	Language	Result	Execution time	Memory
743778		Mauve	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	18 ms	3148 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1e18
#define buy first
#define sell second
#define list shaa
ll n,m,l,r,i,j,ii,jj,k,dp[101][101],ans;
pair<ll,ll> list[101][1001];
int main(){
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cin>>n>>m>>k;
	for(i=1;i<=n;i++)
	for(j=1;j<=k;j++){
		cin>>l>>r;
		list[i][j]={l,r};
	 }
	for(i=1;i<=n;i++) for(j=1;j<=n;j++) dp[i][j]=INF;
	for(i=1;i<=m;i++){
         cin>>l>>r>>jj;
         dp[l][r]=min(dp[l][r],jj);
	}
	for(ii=1;ii<=n;ii++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	dp[i][j]=min(dp[i][j],dp[i][ii]+dp[ii][j]);
	for(ii=1;ii<=k;ii++)
	for(i=2;i<=n;i++)
	if(list[1][ii].buy!=-1 && list[i][ii].sell!=-1) ans=max(ans,(list[i][ii].sell-list[1][ii].buy)/(dp[1][i]+dp[i][1]));
	cout<<ans;
}

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