Submission #568596

#	Time	Username	Problem	Language	Result	Execution time	Memory
568596		inluminas	Travelling Merchant (APIO17_merchant)	C++14	33 / 100	149 ms	2120 KiB

merchant

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

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
#define l first
#define r second

const int lmt=101;
vector<pair<ll,ll>>adj[lmt];
ll b[lmt][1001],s[lmt][1001],dis[lmt][lmt],val[lmt][lmt],n,m,k,mx[lmt][lmt];

bool ok(ll x){
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			val[i][j]=-2e9;
			if(dis[i][j]>=2e9) continue;
			val[i][j]=max(val[i][j],-dis[i][j]*x+mx[i][j]);
		}
	}

	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int l=1;l<=n;l++){
				if(dis[i][l]>=2e9 || dis[l][j]>=2e9) continue;
				val[i][j]=max(val[i][j],val[i][l]+val[l][j]);
			}
		}
	}

	for(int i=1;i<=n;i++){
		if(val[i][i]>=0) return true;
	}

	return false;
}

int main(){
	fastio;

	cin>>n>>m>>k;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++) dis[i][j]=2e9;
	}
	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++){
		ll u,v,w;
		cin>>u>>v>>w;
		dis[u][v]=w;
	}

	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int l=1;l<=n;l++){
				dis[i][j]=min(dis[i][j],dis[i][l]+dis[l][j]);
			}
		}
	}

	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(dis[i][j]==2e9){
				mx[i][j]=-2e9;
				continue;
			}
			for(int l=1;l<=k;l++){
				if(s[j][l]==-1 || b[i][l]==-1) continue;
				mx[i][j]=max(mx[i][j],s[j][l]-b[i][l]);
			}
		}
	}

	ll lo=0,hi=1e9;
	while(hi-lo>1){
		ll mid=(lo+hi)>>1;
		if(ok(mid)) lo=mid;
		else hi=mid;
	}

	if(ok(hi)) cout<<hi<<endl;
	else cout<<lo<<endl;

	return 0;
}

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