Submission #73421

#	Time	Username	Problem	Language	Result	Execution time	Memory
73421		FedericoS	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	1078 ms	3448 KiB

merchant

#include <iostream>
using namespace std;
typedef long long int ll;

ll INF=1e15;
ll N,M,K;
ll x,y;
ll C[100][1005][2];
ll D[105][105];
ll P[105][105];
ll DP[55][55][55];
bool B[55][55][55];

int main(){

	cin>>N>>M>>K;
	for(ll i=0;i<N;i++)
		for(ll j=0;j<K;j++)
			cin>>C[i][j][0]>>C[i][j][1];

	for(ll i=0;i<N;i++)
		for(ll j=0;j<N;j++)
			D[i][j]=(i==j)?0:INF;

	for(ll i=0;i<M;i++)
		cin>>x>>y>>D[x-1][y-1];

	for(ll k=0;k<N;k++)
		for(ll i=0;i<N;i++)
			for(ll j=0;j<N;j++)
				D[i][j]=min(D[i][j],D[i][k]+D[k][j]);

	for(ll a=0;a<N;a++)
		for(ll b=0;b<N;b++)
			for(ll j=0;j<K;j++)
				if(C[a][j][0]!=-1 and C[b][j][1]!=-1)
					P[a][b]=max(P[a][b],C[b][j][1]-C[a][j][0]);

	/*******************/

	for(ll k=1;k<N;k++)
		for(ll a=0;a<N;a++)
			for(ll b=0;b<N;b++)
				DP[a][b][k]=-1;

	for(ll a=0;a<N;a++)
		for(ll b=0;b<N;b++)
			if(a!=b and D[a][b]==1)
				DP[a][b][1]=P[a][b];

	for(ll k=2;k<N;k++)
		for(ll i=1;i<k;i++)
			for(ll a=0;a<N;a++)
				for(ll b=0;b<N;b++)
					for(ll c=0;c<N;c++){
						int j=k-i;
						B[a][b][i+j]|=B[a][c][i] && B[c][b][j];
					}

	for(ll k=2;k<N;k++)
		for(ll i=1;i<k;i++)
			for(ll a=0;a<N;a++)
				for(ll b=0;b<N;b++){
					if(B[a][b][k])
						DP[a][b][k]=P[a][b];
					for(ll c=0;c<N;c++){
						ll j=k-i;
						if(i+j<N and a!=b and b!=c and a!=c and DP[a][c][i]!=-1 and DP[c][b][j]!=-1)
							DP[a][b][i+j]=max(DP[a][b][i+j],DP[a][c][i]+DP[c][b][j]);
					}
				}
	
	/*****************?*/						

	ll ans=0;

	for(ll a=0;a<N;a++)
		for(ll b=0;b<N;b++)
			for(ll i=1;i<N;i++)
				for(ll j=1;j<N;j++)
					ans=max(ans,(DP[a][b][i]+DP[b][a][j])/(i+j));

	/*for(ll a=0;a<N;a++)
		for(ll b=0;b<N;b++)
			cout<<a<<" "<<b<<" "<<P[a][b]<<endl;

	for(ll a=0;a<N;a++)
		for(ll b=0;b<N;b++)
			for(ll i=1;i<N;i++)
				cout<<a<<" "<<b<<" "<<i<<" "<<DP[a][b][i]<<endl;*/

/*
	for(ll i=1;i<N;i++)
		ans=max(ans,(P[0][i]+P[i][0])/(D[0][i]+D[i][0]));
*/
	cout<<ans;

}
	/*for(ll a=0;a<N;a++)
		for(ll b=0;b<N;b++)
			cout<<a<<" "<<b<<" "<<P[a][b]<<endl;*/

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