// vim: foldmethod=marker
// Sat Feb 15 23:04:31 MSK 2020: start
// Sat Feb 15 23:15:57 MSK 2020: done coding
// Sat Feb 15 23:26:12 MSK 2020: ok samples.
#include <bits/stdc++.h>
using namespace std;
#define llong long long
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define rand __rand
mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); // or mt19937_64
template<class T = int> T rand(T range = numeric_limits<T>::max()) { return (T)(rng() % range); }
/*{{{*/
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG
int debug = 1;
#define DB(...) stringstream CONCAT(ss, __LINE__); CONCAT(ss, __LINE__) << __VA_ARGS__; debug_block CONCAT(dbbl, __LINE__)(CONCAT(ss, __LINE__).str())
#else
int debug = 0;
#define DB(...)
#endif
int __db_level = 0;
#define clog if (debug) cerr << string(__db_level * 2, ' ')
struct debug_block {
string name;
debug_block(const string& name_): name(name_) { clog << "{ " << name << endl; ++__db_level; }
~debug_block() { --__db_level; clog << "} " << name << endl; }
};
#define deb(...) "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]"
#define debln(...) clog << "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]" << endl
#define _ << ", " <<
template<class U, class V>
ostream& operator<<(ostream& out, const pair<U, V>& p) { return out << "(" << p.first _ p.second << ")"; }
template<class A, class B>
ostream& operator<<(ostream& out, const tuple<A, B>& t) { return out << "(" << get<0>(t) _ get<1>(t) << ")"; }
template<class A, class B, class C>
ostream& operator<<(ostream& out, const tuple<A, B, C>& t) { return out << "(" << get<0>(t) _ get<1>(t) _ get<2>(t) << ")"; }
template<class T> ostream& operator<<(ostream& out, const vector<T>& container) {
out << "{";
if (len(container)) out << container[0];
rep1(i, len(container) - 1) out _ container[i];
return out << "}";
}
template<class x> vector<typename x::value_type> $v(const x& a) { return vector<typename x::value_type>(a.begin(), a.end()); }
#define ptrtype(x) typename iterator_traits<x>::value_type
template<class u> vector<ptrtype(u)> $v(u a, u b) { return vector<ptrtype(u)>(a, b); }
/*}}}*/
// ACTUAL SOLUTION BELOW ////////////////////////////////////////////////////////////
const int maxn = 111;
const int maxk = 1010;
const llong inf = (llong)1e12;
int n, m, k;
llong buy_cost[maxn][maxk], sell_cost[maxn][maxk];
llong dist[maxn][maxn];
llong profit[maxn][maxn];
llong cur_ans[maxn][2];
bool in_queue[maxn][2];
int cnt_vis[maxn][2];
bool check(llong ans) {
// DB("check " << ans);
rep1(i, n) {
cur_ans[i][0] = cur_ans[i][1] = -inf;
cnt_vis[i][0] = cnt_vis[i][1] = 0;
in_queue[i][0] = in_queue[i][1] = false;
}
queue<pair<int, int>> qu;
for (qu.emplace(1, 0), cur_ans[1][0] = 0, in_queue[0][0] = 1; len(qu); qu.pop()) {
auto [u, holding] = qu.front();
// DB(deb(u _ holding));
++cnt_vis[u][holding];
in_queue[u][holding] = false;
// debln(cnt_vis[u][holding] _ cur_ans[u][holding]);
if (cnt_vis[u][holding] > n * 2) return true;
rep1(v, n) {
llong new_dist = cur_ans[u][holding] - dist[u][v] * ans;
if (holding) new_dist += profit[u][v];
if (new_dist <= cur_ans[v][!holding]) continue;
cur_ans[v][!holding] = new_dist;
// debln(v _ !holding _ new_dist _ dist[u][v] _ (-dist[u][v] * ans));
if (!in_queue[v][!holding]) {
qu.emplace(v, !holding);
in_queue[v][!holding] = true;
}
}
}
return false;
}
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
// debln(n _ m _ k);
rep1(i, n) {
dist[i][i] = 0;
for (int f = i + 1; f <= n; ++f)
dist[i][f] = dist[f][i] = inf;
}
rep1(i, n) rep(f, k) {
cin >> buy_cost[i][f] >> sell_cost[i][f];
}
rep(i, m) {
int u, v; llong d;
cin >> u >> v >> d;
dist[u][v] = min(dist[u][v], d);
}
rep1(mid, n) rep1(u, n) rep1(v, n) {
dist[u][v] = min(dist[u][mid] + dist[mid][v], dist[u][v]);
}
memset(profit, 0, sizeof(profit));
rep(thing, k) {
rep1(u, n) {
if (buy_cost[u][thing] == -1) continue;
rep1(v, n) {
if (sell_cost[v][thing] == -1) continue;
profit[u][v] = max(profit[u][v], sell_cost[v][thing] - buy_cost[u][thing]);
}
}
}
llong low = 0, high = 1;
while (check(high)) high <<= 1;
while (low < high) {
llong mid = low + (high - low + 1) / 2;
if (check(mid)) low = mid;
else high = mid - 1;
}
cout << low;
return 0;
}
Compilation message
merchant.cpp: In function 'bool check(long long int)':
merchant.cpp:76:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
auto [u, holding] = qu.front();
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
384 ms |
1404 KB |
Output is correct |
| 4 |
Correct |
36 ms |
888 KB |
Output is correct |
| 5 |
Correct |
28 ms |
888 KB |
Output is correct |
| 6 |
Correct |
6 ms |
888 KB |
Output is correct |
| 7 |
Correct |
45 ms |
888 KB |
Output is correct |
| 8 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
888 KB |
Output is correct |
| 2 |
Correct |
44 ms |
888 KB |
Output is correct |
| 3 |
Correct |
24 ms |
888 KB |
Output is correct |
| 4 |
Correct |
22 ms |
888 KB |
Output is correct |
| 5 |
Correct |
58 ms |
1016 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
632 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
1668 KB |
Output is correct |
| 2 |
Correct |
412 ms |
3944 KB |
Output is correct |
| 3 |
Correct |
373 ms |
1528 KB |
Output is correct |
| 4 |
Correct |
117 ms |
1656 KB |
Output is correct |
| 5 |
Incorrect |
463 ms |
1740 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
888 KB |
Output is correct |
| 2 |
Correct |
44 ms |
888 KB |
Output is correct |
| 3 |
Correct |
24 ms |
888 KB |
Output is correct |
| 4 |
Correct |
22 ms |
888 KB |
Output is correct |
| 5 |
Correct |
58 ms |
1016 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
632 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
