Submission #102002

#	Time	Username	Problem	Language	Result	Execution time	Memory
102002		bakpark	Travelling Merchant (APIO17_merchant)	C++14	33 / 100	134 ms	1400 KiB

merchant

#include <cstdio>
#include <algorithm>
#include <limits.h>
#include <memory.h>
using namespace std;
#define ll long long

int N,M,K;
int B[101][1001], S[101][1001], T[101][101];
double val[101][101];
int Q[101][101];
ll dist[101][101];
double g(int st,int en,int m,ll d){
	return Q[st][en]-(double)d*m;
}
bool f(int m){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			if(T[i][j]) {
				dist[i][j] = T[i][j];
				val[i][j] = g(i,j,m,dist[i][j]);
			}
			else {
				dist[i][j] = -1ll;
				val[i][j] = LLONG_MIN;
			}
		}
	}
	for(int mid=1;mid<=N;mid++){
		for(int st=1;st<=N;st++){
			for(int en=1;en<=N;en++){
				if(dist[st][mid]==-1ll||dist[mid][en]==-1ll) continue;
				ll td = dist[st][mid]+dist[mid][en];
				double hval = max(g(st,en,m,td),val[st][mid]+val[mid][en]);
				if(hval>val[st][en]){
					dist[st][en] = td;
					val[st][en] = hval;
				}
			}
		}
		for(int n=1;n<=N;n++){
			if(val[n][n]>=0) return true;
		}
	}
	return false;
}
int main(){
	scanf("%d %d %d",&N,&M,&K);
	for(int i=1;i<=N;i++){
		for(int j=0;j<K+K;j++){
			int tmp;scanf("%d",&tmp);
			if(j&1)	S[i][j/2+1] = tmp;
			else B[i][j/2+1] = tmp;
		}
	}
	for(int i=0;i<M;i++){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		T[a][b] = c;
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			for(int k=1;k<=K;k++){
				if(i==j) continue;
				if(B[i][k]>0&&S[j][k]>0)
					Q[i][j] = max(Q[i][j],S[j][k]-B[i][k]);
			}
		}
	}
	int l = 0,r = 1000000000,answ=0;
	while(l<=r){
		int m = (l+r)>>1;
		if(f(m)){
			l = m+1;
			answ = m;
		}
		else r = m-1;
	}
	printf("%d",answ);
}
		

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:48: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:51:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int tmp;scanf("%d",&tmp);
            ~~~~~^~~~~~~~~~~
merchant.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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