Submission #1196306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196306		nouka28	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	57 ms	2120 KiB

merchant

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

// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;

signed main(){
	int N,M,K;cin>>N>>M>>K;

	vector<vector<int>> B(N,vector<int>(K)),S(N,vector<int>(K));
	rep(i,N){
		rep(j,K){
			cin>>B[i][j];
			cin>>S[i][j];
		}
	}



	vector<vector<int>> d(N,vector<int>(N,1e18));
	rep(i,N)d[i][i]=0;
	rep(i,M){
		int v,w,t;cin>>v>>w>>t;v--;w--;
		d[v][w]=min(d[v][w],t);
	}
	rep(k,N)rep(i,N)rep(j,N){
		d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	}

	vector<vector<int>> mxd(N,vector<int>(N,0));
	rep(i,N)rep(j,N){
		rep(k,K){
			if(B[i][k]!=-1&&S[j][k]!=-1)mxd[i][j]=max(mxd[i][j],S[j][k]-B[i][k]);
		}
	}

	// int ans=0;
	// rng(i,1,N){
	// 	if(d[0][i]==1e18)continue;

	// 	// cout<<i<<" : "<<mxd[0][i]<<" "<<d[0][i]<<endl;
	// 	ans=max(ans,mxd[0][i]/(d[0][i]+d[i][0]));
	// }

	// cout<<ans<<endl;
	// return 0;

	// rep(i,N){
	// 	cout<<i<<" : ";
	// 	rep(j,N)cout<<mxd[i][j]<<" ";
	// 	cout<<endl;
	// }

	auto judge=[&](int val)->bool {
		vector<vector<int>> dif(N,vector<int>(N));
		rep(i,N)rep(j,N){
			if(i==j)dif[i][j]=1e18;
			else{
				if(d[i][j]==1e18)dif[i][j]=1e18;
				else dif[i][j]=val*d[i][j]-mxd[i][j];
			}
		}
		rep(k,N)rep(i,N)rep(j,N){
			dif[i][j]=min(dif[i][j],dif[i][k]+dif[k][j]);
		}
		rep(i,N){
			if(dif[i][i]<=0){
				return 1;
			}
		}
		return 0;
	};

	int ok=0,ng=1e9+1;
	while(abs(ok-ng)>1){
		int mid=(ok+ng)>>1;
		if(judge(mid))ok=mid;
		else ng=mid;
	}
	cout<<ok<<endl;
}

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