Submission #235095

#	Time	Username	Problem	Language	Result	Execution time	Memory
235095		thtsshz_bgwrswh	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	139 ms	2428 KiB

merchant

#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<vector> 
#include<algorithm> 
using namespace std;
struct Edge{
	long long to,d,p;
};
vector<Edge> g[105];
long long n,m,amount,num[105][1005][2],dis[105][105];
bool check(long long v){
	long long i,j,k;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			dis[i][j]=1000000000000000;
	//for(i=1;i<=n;i++)
	//	dis[i][i]=0;
	for(i=1;i<=n;i++)
		for(auto x:g[i])
			dis[i][x.to]=v*x.d-x.p;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				if(dis[j][k]>dis[j][i]+dis[i][k])
					dis[j][k]=dis[j][i]+dis[i][k];
	for(i=1;i<=n;i++)
		if(dis[i][i]<=0)
			return 1;
	return 0;
}
int main(){
	long long i,j,k,v,w,t;
	scanf("%lld%lld%lld",&n,&m,&amount);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			dis[i][j]=1000000000000000;
	for(i=1;i<=n;i++)
		for(j=1;j<=amount;j++)
			scanf("%lld%lld",&num[i][j][0],&num[i][j][1]);//buy sell
	for(i=1;i<=n;i++)
		dis[i][i]=0;
	for(i=0;i<m;i++){
		scanf("%lld%lld%lld",&v,&w,&t);
		dis[v][w]=min(dis[v][w],t);
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				if(dis[j][k]>dis[j][i]+dis[i][k])
					dis[j][k]=dis[j][i]+dis[i][k];
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j||dis[i][j]==1000000000000000)
				continue;
			long long maxv=0;
			for(k=1;k<=amount;k++){
				if(num[i][k][0]==-1||num[j][k][1]==-1)
					continue;
				maxv=max(maxv,num[j][k][1]-num[i][k][0]);
			}
			g[i].emplace_back((Edge){j,dis[i][j],maxv});
		} 
	}
	long long left=-1,right=1000000005;
	while(right-left>1){
		long long mid=(right+left)>>1;
		if(check(mid))
			left=mid;
		else
			right=mid;
	}
	printf("%lld\n",left);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&m,&amount);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:39:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld",&num[i][j][0],&num[i][j][1]);//buy sell
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&v,&w,&t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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