Submission #64254

#	Time	Username	Problem	Language	Result	Execution time	Memory
64254		khohko	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	399 ms	12400 KiB

merchant

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define ARRS ((ll)(2e6+500))
#define MAX ((ll)(1e12+100))
#define MOD ((ll)1e6+7)
#define mi(a,b) a=min((a),(b))


ll n,m,k;
pair<ll,ll> q[2000][2000];
__int128 f[2000][2000];
__int128 v[2000][2000];
__int128 ve[2000][2000];


int main(){
	#ifdef KHOKHO
			freopen("in.in","r",stdin);
			freopen("out.out","w",stdout);
	#endif
	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	//cout<<n<<" "<<k<<endl;
	for(int i=0; i<n; i++)
		for(int j=0; j<k; j++)
			cin>>q[i][j].fr>>q[i][j].sc;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			f[i][j]=f[j][i]=MAX;
	for(int i=0; i<m; i++){
		ll k,p,c;
		cin>>k>>p>>c;
		k--;
		p--;
		f[k][p]=c;
	}
	//return 0;
	for(int k=0; k<n; k++)
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			ve[i][j]=0;
			for(int t=0; t<k; t++){
				if(q[i][t].fr>=0&&q[j][t].sc>=0)
					ve[i][j]=max(ve[i][j],(__int128)q[j][t].sc-q[i][t].fr);
			}
		}
	}
	ll l=0,r=MAX;
	while(l<r){
		ll em=(l+r+1)>>1ll;
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				v[i][j]=ve[i][j]-em*f[i][j];
		for(int k=0; k<n; k++){
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					v[i][j]=max(v[i][j],v[i][k]+v[k][j]);
				}
			}
		}
		bool e=0;
		for(int i=0; i<n; i++){
			if(v[i][i]>=0)
				e=1;
		}
		if(e)
			l=em;
		else r=em-1;
	}
	ll t=l;
	cout<<t;

}

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