oj.uz

Submission #118937

# Submission time Handle Problem Language Result Execution time Memory
118937 2019-06-20T05:37:38 Z Mahdi_Jfri Travelling Merchant (APIO17_merchant) C++14
0 / 100
 62 ms 1408 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e2 + 20;
const int maxm = 1e4 + 20;
const int maxk = 1e3 + 20;

int b[maxn][maxk] , s[maxn][maxk];

int d[maxn][maxn] , best[maxn][maxn] , n;

ll res[maxn][maxn];

bool check(ll x)
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			res[i][j] = d[i][j] * x - best[i][j];

	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				res[i][j] = min(res[i][j] , res[i][k] + res[k][j]);

	for(int i = 0; i < n; i++)
		for(int j = i + 1; j < n; j++)
			if(res[i][j] + res[j][i] <= 0)
				return 1;

	return 0;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int m , k;
	cin >> n >> m >> k;

	for(int i = 0; i < n; i++)
		for(int j = 0; j < k; j++)
			cin >> b[i][j] >> s[i][j];

	memset(d , 63 , sizeof d);
	for(int i = 0; i < m; i++)
	{
		int a , b , c;
		cin >> a >> b >> c;
		a-- , b--;

		d[a][b] = min(d[a][b] , c);
	}

	for(int i = 0; i < n; i++)
		d[i][i] = 0;

	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				d[i][j] = min(d[i][j] , d[i][k] + d[k][j]);

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			for(int ind = 0; ind < k; ind++)
				if(b[i][ind] != -1 && s[j][ind] != -1)
					best[i][j] = max(best[i][j] , s[j][ind] - b[i][ind]);

	int l = 0 , r = 2e9;

	while(r - l > 1)
	{
		int m = (l + r) / 2;
		if(check(m))
			l = m;
		else
			r = m;
	}

	cout << l << endl;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1280 KB Output is correct
2 Correct 36 ms 1280 KB Output is correct
3 Incorrect 36 ms 1280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 8 ms 896 KB Output is correct
8 Correct 7 ms 896 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 7 ms 896 KB Output is correct
11 Correct 7 ms 896 KB Output is correct
12 Correct 8 ms 896 KB Output is correct
13 Incorrect 7 ms 896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 896 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 8 ms 896 KB Output is correct
8 Correct 7 ms 896 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 7 ms 896 KB Output is correct
11 Correct 7 ms 896 KB Output is correct
12 Correct 8 ms 896 KB Output is correct
13 Incorrect 7 ms 896 KB Output isn't correct
14 Halted 0 ms 0 KB -