oj.uz

Submission #84266

# Submission time Handle Problem Language Result Execution time Memory
84266 2018-11-14T04:09:38 Z shoemakerjo Travelling Merchant (APIO17_merchant) C++14
33 / 100
 119 ms 2664 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 = 1e18;

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*min(inf/val, dist[i][j]);
		}
		
	}
	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 = 1e12;
	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 Correct 84 ms 2040 KB Output is correct
2 Correct 53 ms 2040 KB Output is correct
3 Correct 54 ms 2040 KB Output is correct
4 Incorrect 10 ms 2040 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 2040 KB Output is correct
2 Correct 119 ms 2664 KB Output is correct
3 Correct 56 ms 2664 KB Output is correct
4 Correct 62 ms 2664 KB Output is correct
5 Correct 60 ms 2664 KB Output is correct
6 Correct 56 ms 2664 KB Output is correct
7 Correct 16 ms 2664 KB Output is correct
8 Correct 2 ms 2664 KB Output is correct
9 Correct 11 ms 2664 KB Output is correct
10 Correct 11 ms 2664 KB Output is correct
11 Correct 15 ms 2664 KB Output is correct
12 Correct 10 ms 2664 KB Output is correct
13 Correct 10 ms 2664 KB Output is correct

Subtask #4
0 / 34.0

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