Submission #732892

#	Time	Username	Problem	Language	Result	Execution time	Memory
732892		1ne	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	97 ms	4256 KiB

merchant

/*
*  author : Apiram                  
*  created: 29.04.2023 02:41:46
*/

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m,k;cin>>n>>m>>k;
	vector<vector<long long>>b(n),s(n);
	for (int i = 0;i<n;++i){
		for (int j = 0;j<k;++j){
			long long x,y;cin>>x>>y;
			b[i].push_back(x);
			s[i].push_back(y);
		}
	}
	vector<vector<long long>>mxprofit(n,vector<long long>(n,0));                                         
	vector<vector<long long>>dist(n,vector<long long>(n,1e16));
	for (int i = 0;i<m;++i){
		long long x,y,cost;
		cin>>x>>y>>cost;
		--x;--y;
		dist[x][y] = min(dist[x][y],cost);	
	}
	for (int i = 0;i<n;++i){
		for (int j = 0;j<n;++j){
			for (int p = 0;p<k;++p){
				if (b[i][p] == -1 || s[j][p] == -1)continue;
				mxprofit[i][j] = max(mxprofit[i][j],(s[j][p] - b[i][p]));
			}
		}
	}
	for (int i = 0;i<n;++i){
		for (int j = 0;j<n;++j){
			for (int p = 0;p<n;++p){
				dist[j][p] = min(dist[j][p],dist[j][i] + dist[i][p]);
			}
		}
	}
	long long ans = 0;
	long long left = 0,right = 1e9;
	while(left<=right){
		long long mid = (left + right)>>1;
		//profit / time >= mid
		//profit >= mid * time
		//-profit + mid * time <= 0
		vector<vector<long long>>cost(n,vector<long long>(n,1e16));
		for (int i = 0;i<n;++i){
			for (int j = 0;j<n;++j){
				if (dist[i][j] == 1e16)continue;
				cost[i][j] = mid * dist[i][j] - mxprofit[i][j];
			}
		}
		for (int i = 0;i<n;++i){
			for (int j = 0;j<n;++j){
				for (int p = 0;p<n;++p){
					cost[j][p] = min(cost[j][i] + cost[i][p],cost[j][p]);
				}
			}
		}
		bool ok = false;
		for (int i = 0;i<n;++i){
			if (cost[i][i] <= 0){
				ok = true;
			}
		}
		if (ok){
			left = mid + 1;
			ans = mid;
		} 
		else{
			right = mid - 1;
		}
	}	
	cout<<ans<<'\n';		
	return 0;
}

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