oj.uz

Submission #49745

# Submission time Handle Problem Language Result Execution time Memory
49745 2018-06-02T14:17:39 Z top34051 Travelling Merchant (APIO17_merchant) C++17
0 / 100
 122 ms 2168 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;

int n,m,k;
long long a[105][1005], b[105][1005];
long long profit[105][105], dist[105][105];
long long ok[105][105];

bool check(long long val) {
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			if(profit[i][j]==-inf || dist[i][j]==inf) ok[i][j] = -inf;
			else ok[i][j] = profit[i][j] - val * dist[i][j];
		}
	}
	for(int x=1;x<=n;x++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				ok[i][j] = max(ok[i][j], ok[i][x] + ok[x][j]);
			}
		}
	}
	for(int i=1;i<=n;i++) if(ok[i][i]>=0) return 1;
	return 0;
}

int main() {
	int i,j,x,y;
	long long val;

	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=k;j++) {
			scanf("%lld%lld",&a[i][j],&b[i][j]);
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			dist[i][j] = inf;
			profit[i][j] = -inf;
		}
	}
	for(int i=1;i<=m;i++) {
		scanf("%d%d%lld",&x,&y,&val);
		dist[x][y] = min(dist[x][y], val);
		dist[y][x] = min(dist[y][x], val);
	}

	//get dist[x][y]
	for(int x=1;x<=n;x++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
			}
		}
	}

	//get profit[x][y]
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			for(int x=1;x<=k;x++) {
				if(a[i][x]==-1 || b[j][x]==-1) continue;
				profit[i][j] = max(profit[i][j], b[j][x] - a[i][x]);
			}
		}
	}

	//find answer
	long long l = 0, r = inf, mid, ans;
	while(l<=r) {
		mid = (l+r)/2;
		if(check(mid)) {
			ans = mid;
			l = mid+1;
		}
		else r = mid-1;
	}
	printf("%lld",ans);
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:30:6: warning: unused variable 'i' [-Wunused-variable]
  int i,j,x,y;
      ^
merchant.cpp:30:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,x,y;
        ^
merchant.cpp:33: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:36:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld",&a[i][j],&b[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld",&x,&y,&val);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -