Submission #49964

#	Time	Username	Problem	Language	Result	Execution time	Memory
49964		hamzqq9	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	119 ms	1788 KiB

merchant

#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 4000000000000000000ll
#define M 10000002
#define N 105
#define LOG 20
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
using namespace std;

int n,m,k,x,y,z;
int b[N][N*10],s[N][N*10];
ll p[N][N],d1[N][N],d2[N][N];

bool neg(int pro) {

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			if(d1[i][j]==inf) d2[i][j]=inf;
			else d2[i][j]=1ll*d1[i][j]*pro-p[i][j];

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			for(int k=1;k<=n;k++) {

				umin(d2[j][k],d2[j][i]+d2[i][k]);

			}

		}

	}

	for(int i=1;i<=n;i++) {

		if(d2[i][i]<=0) return true;

	}

	return false;

}

int main() {
 
 	#if 0
	freopen("input.txt","r",stdin);
 	#endif

	scanf("%d %d %d",&n,&m,&k);

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=k;j++) {

			scanf("%d %d",&b[i][j],&s[i][j]);

		}

	}	

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			d1[i][j]=inf;

		}

	}

	for(int i=1;i<=m;i++) {

		scanf("%d %d %d",&x,&y,&z);

		umin(d1[x][y],1ll*z);

	}

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			for(int k=1;k<=n;k++) {

				umin(d1[j][k],d1[j][i]+d1[i][k]);

			}

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			for(int g=1;g<=k;g++) {

				if(~s[j][g] && ~b[i][g]) {

					umax(p[i][j],1ll*s[j][g]-b[i][g]);
				
				}	
			
			}

		}

	}

	/*for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%d ",p[i][j]);

		printf("\n\n\n\n");

	for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%lld ",d1[i][j]);*/

	int bas=1,son=1e9;

	while(bas<=son) {

		if(neg(orta)) bas=orta+1;
		else son=orta-1;

	}

	printf("%d",son);

	//printf("%lld",LONG_LONG_MAX);

}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
merchant.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&b[i][j],&s[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&y,&z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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