oj.uz

Submission #249405

# Submission time Handle Problem Language Result Execution time Memory
249405 2020-07-14T22:14:04 Z godwind Travelling Merchant (APIO17_merchant) C++14
33 / 100
 662 ms 4092 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <functional>
//#include <unordered_map>

using namespace std;

template<typename T> void uin(T &a, T b) {if (b < a) a = b;}
template<typename T> void uax(T &a, T b) {if (b > a) a = b;}

#define int long long
#define double long double
#define left left228
#define right right228
#define mp make_pair
#define all(v) v.begin(), v.end()

const int N = 105, K = 1005;
const double eps = 1e-6;
const int INF = 1e18 + 228;

int n, m, k;
int buy[N][K], sell[N][K];

vector< pair<int, int> > g[N];

int dist[N][N];
int max_profit[N][N];

void pre() {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			dist[i][j] = INF;
		}
		dist[i][i] = 0;
	}
	for (int v = 1; v <= n; ++v) {
		for (pair<int, int> go : g[v]) {
			int to = go.first;
			int w = go.second;
			uin(dist[v][to], w);
		}
	}
	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (dist[i][k] < INF && dist[k][j] < INF) {
					uin(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 t = 1; t <= k; ++t) {
				if (buy[i][t] != -1 && sell[j][t] != -1) {
					uax(max_profit[i][j], sell[j][t] - buy[i][t]);
				}
			}
		}
	}
}

double d[N][N];

bool gr(double x, double y) {
	return x > y + eps;
}

bool check(double x) {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			d[i][j] = -INF;
		}
	}
	for (int a = 1; a <= n; ++a) {
		for (int b = 1; b <= n; ++b) {
			if (a == b) continue;
			if (dist[a][b] < INF) {
				double weight = (double)max_profit[a][b] - (double)dist[a][b] * x;
				d[a][b] = weight;
			}
		}
	}
	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (d[i][k] > -INF / 2 && d[k][j] > -INF / 2) {
					uax(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (gr(d[i][i], 0)) {
			return 1;
		}
	}
	return 0;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= k; ++j) {
			cin >> buy[i][j] >> sell[i][j];
		}
	}
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
	}
	pre();
	double l = 0, r = 1e18;
	for (int i = 0; i < 100; ++i) {
		if (abs(r - l) <= eps) break;
		double M = (l + r) / 2.0;
		if (check(M)) {
			l = M;
		} else {
			r = M;
		}
	}
	cout << setprecision(15) << (int)r << '\n';
	return 0;
}

/*


*/

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 3452 KB Output is correct
2 Incorrect 367 ms 1528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 896 KB Output is correct
2 Correct 61 ms 896 KB Output is correct
3 Correct 54 ms 1024 KB Output is correct
4 Correct 51 ms 1012 KB Output is correct
5 Correct 78 ms 1024 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 1912 KB Output is correct
2 Correct 654 ms 4092 KB Output is correct
3 Correct 533 ms 1664 KB Output is correct
4 Correct 523 ms 1912 KB Output is correct
5 Correct 660 ms 1792 KB Output is correct
6 Correct 431 ms 1664 KB Output is correct
7 Correct 89 ms 1024 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 87 ms 1144 KB Output is correct
10 Correct 67 ms 1024 KB Output is correct
11 Correct 51 ms 1144 KB Output is correct
12 Correct 58 ms 1024 KB Output is correct
13 Correct 46 ms 896 KB Output is correct

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 896 KB Output is correct
2 Correct 61 ms 896 KB Output is correct
3 Correct 54 ms 1024 KB Output is correct
4 Correct 51 ms 1012 KB Output is correct
5 Correct 78 ms 1024 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -