Submission #1191015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191015		boclobanchat	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	66 ms	2120 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
const long long INF=1e18;
long long dp[105][105],S[105][1005],B[105][1005],F[105][105],P[105][105];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=1e9*(i!=j);
	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<=m;i++)
	{
		int l,r,v;
		cin>>l>>r>>v;
		dp[l][r]=min(dp[l][r],(long long)v);
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
	{
		F[i][j]=0;
		for(int l=1;l<=k;l++) if(B[i][l]!=-1&&S[j][l]!=-1) F[i][j]=max(F[i][j],S[j][l]-B[i][l]);
	}
	int l=0,r=1e9,ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		bool ck=false;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) P[i][j]=dp[i][j]*mid-F[i][j];
		for(int i=1;i<=n;i++) P[i][i]=INF;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) P[j][k]=min(P[j][k],max(-INF,P[j][i]+P[i][k]));
		for(int i=1;i<=n;i++) ck|=(P[i][i]<=0);
		if(ck) l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<ans;
}

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