#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
namespace debug {
const int DEBUG = true;
template<class T1, class T2>
void pr(const pair<T1, T2> &x);
template<class T, size_t SZ>
void pr(const array<T, SZ> &x);
template<class T>
void pr(const vector<T> &x);
template<class T>
void pr(const set<T> &x);
template<class T1, class T2>
void pr(const map<T1, T2> &x);
template<class T>
void pr(const T &x) { if (DEBUG) cout << x; }
template<class T, class... Ts>
void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }
template<class T1, class T2>
void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }
template<class T>
void prIn(const T &x) {
pr("{");
bool fst = 1;
for (auto &a : x) {
pr(fst ? "" : ", ", a), fst = 0;
}
pr("}");
}
template<class T, size_t SZ>
void pr(const array<T, SZ> &x) { prIn(x); }
template<class T>
void pr(const vector<T> &x) { prIn(x); }
template<class T>
void pr(const set<T> &x) { prIn(x); }
template<class T1, class T2>
void pr(const map<T1, T2> &x) { prIn(x); }
void ps() { pr("\n"), cout << flush; }
template<class Arg, class... Args>
void ps(const Arg &first, const Args &... rest) {
pr(first, " ");
ps(rest...);
}
}
using namespace debug;
const int MAXN = 105;
const int MAXK = 1005;
const ll INF = 1e12;
ll aM[MAXN][MAXN];
ll trans[2][MAXN][MAXK]; // 0 is buy 1 is sell
ll prof[MAXN][MAXN];
ld agg[MAXN][MAXN];
ld best[MAXN];
int N, M, K;
bool pos(ld ef) {
assert(ef > 0);
// ps(ef);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
agg[i][j] = prof[i][j] - aM[i][j] * ef;
}
}
fill(best, best + MAXN, 0);
for (int i = 0; i < N; i++) {
for (int cV = 0; cV < N; cV++) {
for (int aV = 0; aV < N; aV++) {
if (best[aV] < best[cV] + agg[cV][aV]) {
best[aV] = best[cV] + agg[cV][aV];
}
}
}
}
for (int cV = 0; cV < N; cV++) {
for (int aV = 0; aV < N; aV++) {
if (best[aV] < best[cV] + agg[cV][aV]) {
return true;
}
}
}
return false;
}
ll binSearch() {
ll low = 0;
ll hi = INF;
while (low != hi) {
ll mid = (low + hi + 1) / 2;
if (pos(mid)) {
low = mid;
} else {
hi = mid - 1;
}
}
if (pos(low + 1 - 1e-9L)) {
return low + 1;
}
return low;
}
int main() {
// freopen("travelling.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
cin >> trans[0][i][j] >> trans[1][i][j];
if (trans[0][i][j] == -1) {
trans[0][i][j] = INF;
}
if (trans[1][i][j] == -1) {
trans[1][i][j] = -INF;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
aM[i][j] = INF;
}
}
// ps("here");
for (int i = 0; i < M; i++) {
int u, v;
ll c;
cin >> u >> v >> c;
u--, v--;
aM[u][v] = c;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (aM[j][i] + aM[i][k] < aM[j][k]) {
aM[j][k] = aM[j][i] + aM[i][k];
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
ll cM = 0;
for (int k = 0; k < K; k++) {
cM = max(cM, trans[1][j][k] - trans[0][i][k]);
}
prof[i][j] = cM;
}
}
// cout << pos(2) << endl;
ll ans = binSearch();
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
230 ms |
2296 KB |
Output is correct |
2 |
Incorrect |
193 ms |
1408 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
896 KB |
Output is correct |
2 |
Correct |
30 ms |
896 KB |
Output is correct |
3 |
Correct |
30 ms |
896 KB |
Output is correct |
4 |
Correct |
29 ms |
896 KB |
Output is correct |
5 |
Correct |
31 ms |
1024 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
30 ms |
896 KB |
Output is correct |
8 |
Correct |
30 ms |
896 KB |
Output is correct |
9 |
Correct |
30 ms |
1024 KB |
Output is correct |
10 |
Correct |
30 ms |
896 KB |
Output is correct |
11 |
Correct |
31 ms |
896 KB |
Output is correct |
12 |
Correct |
33 ms |
988 KB |
Output is correct |
13 |
Correct |
30 ms |
1016 KB |
Output is correct |
14 |
Correct |
31 ms |
896 KB |
Output is correct |
15 |
Correct |
32 ms |
1024 KB |
Output is correct |
16 |
Correct |
30 ms |
896 KB |
Output is correct |
17 |
Correct |
31 ms |
1024 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
33 ms |
1024 KB |
Output is correct |
20 |
Correct |
31 ms |
1024 KB |
Output is correct |
21 |
Correct |
31 ms |
1024 KB |
Output is correct |
22 |
Correct |
31 ms |
768 KB |
Output is correct |
23 |
Correct |
29 ms |
896 KB |
Output is correct |
24 |
Correct |
29 ms |
896 KB |
Output is correct |
25 |
Correct |
32 ms |
1016 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
30 ms |
896 KB |
Output is correct |
28 |
Correct |
30 ms |
896 KB |
Output is correct |
29 |
Correct |
31 ms |
896 KB |
Output is correct |
30 |
Correct |
5 ms |
384 KB |
Output is correct |
31 |
Correct |
31 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
210 ms |
1784 KB |
Output is correct |
2 |
Correct |
233 ms |
2336 KB |
Output is correct |
3 |
Correct |
200 ms |
1536 KB |
Output is correct |
4 |
Correct |
210 ms |
1784 KB |
Output is correct |
5 |
Correct |
204 ms |
1664 KB |
Output is correct |
6 |
Correct |
201 ms |
1664 KB |
Output is correct |
7 |
Correct |
31 ms |
1024 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
33 ms |
1024 KB |
Output is correct |
10 |
Correct |
31 ms |
1024 KB |
Output is correct |
11 |
Correct |
31 ms |
1024 KB |
Output is correct |
12 |
Correct |
31 ms |
768 KB |
Output is correct |
13 |
Correct |
29 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
896 KB |
Output is correct |
2 |
Correct |
30 ms |
896 KB |
Output is correct |
3 |
Correct |
30 ms |
896 KB |
Output is correct |
4 |
Correct |
29 ms |
896 KB |
Output is correct |
5 |
Correct |
31 ms |
1024 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
30 ms |
896 KB |
Output is correct |
8 |
Correct |
30 ms |
896 KB |
Output is correct |
9 |
Correct |
30 ms |
1024 KB |
Output is correct |
10 |
Correct |
30 ms |
896 KB |
Output is correct |
11 |
Correct |
31 ms |
896 KB |
Output is correct |
12 |
Correct |
33 ms |
988 KB |
Output is correct |
13 |
Correct |
30 ms |
1016 KB |
Output is correct |
14 |
Correct |
31 ms |
896 KB |
Output is correct |
15 |
Correct |
32 ms |
1024 KB |
Output is correct |
16 |
Correct |
30 ms |
896 KB |
Output is correct |
17 |
Correct |
210 ms |
1784 KB |
Output is correct |
18 |
Correct |
233 ms |
2336 KB |
Output is correct |
19 |
Correct |
200 ms |
1536 KB |
Output is correct |
20 |
Correct |
210 ms |
1784 KB |
Output is correct |
21 |
Correct |
204 ms |
1664 KB |
Output is correct |
22 |
Correct |
201 ms |
1664 KB |
Output is correct |
23 |
Correct |
31 ms |
1024 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
33 ms |
1024 KB |
Output is correct |
26 |
Correct |
31 ms |
1024 KB |
Output is correct |
27 |
Correct |
31 ms |
1024 KB |
Output is correct |
28 |
Correct |
31 ms |
768 KB |
Output is correct |
29 |
Correct |
29 ms |
896 KB |
Output is correct |
30 |
Correct |
210 ms |
1656 KB |
Output is correct |
31 |
Correct |
208 ms |
1664 KB |
Output is correct |
32 |
Correct |
220 ms |
2432 KB |
Output is correct |
33 |
Correct |
202 ms |
1664 KB |
Output is correct |
34 |
Correct |
210 ms |
1792 KB |
Output is correct |
35 |
Correct |
209 ms |
1792 KB |
Output is correct |
36 |
Correct |
240 ms |
2552 KB |
Output is correct |
37 |
Correct |
5 ms |
512 KB |
Output is correct |
38 |
Correct |
5 ms |
384 KB |
Output is correct |
39 |
Correct |
193 ms |
1536 KB |
Output is correct |
40 |
Correct |
203 ms |
1664 KB |
Output is correct |
41 |
Correct |
201 ms |
1536 KB |
Output is correct |
42 |
Correct |
199 ms |
1536 KB |
Output is correct |
43 |
Correct |
199 ms |
1536 KB |
Output is correct |
44 |
Correct |
5 ms |
384 KB |
Output is correct |
45 |
Correct |
31 ms |
1024 KB |
Output is correct |
46 |
Correct |
31 ms |
1024 KB |
Output is correct |
47 |
Correct |
32 ms |
1024 KB |
Output is correct |
48 |
Correct |
239 ms |
2424 KB |
Output is correct |
49 |
Correct |
249 ms |
2552 KB |
Output is correct |
50 |
Correct |
5 ms |
512 KB |
Output is correct |
51 |
Correct |
230 ms |
2296 KB |
Output is correct |
52 |
Incorrect |
193 ms |
1408 KB |
Output isn't correct |
53 |
Halted |
0 ms |
0 KB |
- |