oj.uz

Submission #111456

# Submission time Handle Problem Language Result Execution time Memory
111456 2019-05-15T11:55:03 Z diamond_duke Travelling Merchant (APIO17_merchant) C++11
0 / 100
 74 ms 1280 KB 
#include <algorithm>
#include <cstring>
#include <cstdio>
using ll = long long;
inline void floyd(ll dis[][105], int n)
{
	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
				dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
		}
	}
}
int buy[105][1005], sell[105][1005], profit[105][105];
ll dis[105][105], cost[105][105];
int main()
{
	// freopen("APIO2017-T3.in", "r", stdin);
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < k; j++)
			scanf("%d", buy[i] + j);
		for (int j = 0; j < k; j++)
			scanf("%d", sell[i] + j);
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int x = 0; x < k; x++)
			{
				if (~buy[i][x] && ~sell[j][x])
					profit[i][j] = std::max(profit[i][j], sell[j][x] - buy[i][x]);
			}
		}
	}
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		dis[--u][--v] = w;
	}
	floyd(dis, n);
	int l = 0, r = 1e9, res = -1;
	while (l <= r)
	{
		int mid = l + r >> 1;
		memset(cost, 0x3f, sizeof(cost));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (dis[i][j] < 1e18)
					cost[i][j] = (ll)dis[i][j] * mid - profit[i][j];
			}
		}
		floyd(cost, n);
		bool flg = false;
		for (int i = 0; i < n; i++)
			flg |= cost[i][i] <= 0;
		if (flg)
		{
			res = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	printf("%d\n", res);
	return 0;
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
merchant.cpp:22: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:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", buy[i] + j);
    ~~~~~^~~~~~~~~~~~~~~~~~
merchant.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", sell[i] + j);
    ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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