oj.uz

Submission #84263

# Submission time Handle Problem Language Result Execution time Memory
84263 2018-11-14T04:04:56 Z shoemakerjo Travelling Merchant (APIO17_merchant) C++14
0 / 100
 106 ms 3492 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define maxn 101
#define maxk 1010
int N, M, K;
const ll inf = 1LL << 60;

ll dist[maxn][maxn];
ll buy[maxn][maxk];
ll sell[maxn][maxk];
ll profit[maxn][maxn];
ll d2[maxn][maxn];

bool check(ll val) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			d2[i][j] = profit[i][j] - val*dist[i][j];
		}
		d2[i][i] = -1;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				d2[i][j] = max(d2[i][j], d2[i][k] + d2[k][j]);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		if (d2[i][i] >= 0) return true;
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dist[i][j] = inf;
		}
		dist[i][i] = inf;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> buy[i][j] >> sell[i][j];
		}
	}
	int vp, wp; ll tp;
	for (int i = 0; i < M; i++) {
		cin >> vp >> wp >> tp;
		dist[vp][wp] = min(dist[vp][wp], tp);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			for (int k = 1; k <= K; k++) {
				if (buy[i][k] == -1 || sell[j][k] == -1) continue;
				profit[i][j] = max(profit[i][j], sell[j][k] - buy[i][k]);
			}
		}
	}

	ll lo = 0LL;
	ll hi = inf;
	while (lo < hi) {
		ll mid = (lo+hi+1)/2LL;
		if (check(mid)) {
			lo = mid;
		}
		else hi = mid-1;
	}
	cout << lo << endl;

}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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