#define OPTIMIZE 0
#define Interactive 0
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int INF = 0x3f3f3f3f; // INF = 0x3f3f3f3f, INT_MAX
const long long MOD = 1e9+7; // MOD = 1e9+7, 1e8+7, 998244353
const long long LINF = 1e18;
#define INIT(arr, val) fill(arr, arr+(int)(sizeof(arr)/sizeof(arr[0])), val)
#define REP(i, lb, rb, inc) for(int i = (lb); i < (rb); i += inc)
#define RREP(i, rb, lb, dec) for(int i = (rb)-1; i >= (lb); i -= dec)
#define REPN(i, s, n) for(int i = s; i < n; ++i)
#define RREPN(i, n, s) for(int i = n-1; i >= s; --i)
typedef long long ll;
typedef std::vector<int> VI;
typedef std::vector<ll> VLL;
typedef std::vector<string> VSTR;
#define pb push_back
typedef std::pair<int, int> PII;
typedef std::pair<double, double> PDD;
typedef std::pair<ll, ll> PLL;
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define SZ(x) ((int)(x).size())
#define endl '\n'
#if !Interactive
# define Foxyy cin.tie(0); cout.sync_with_stdio(0); cout.tie(0);
#else
# define Foxyy ;
#endif
#define I_Suck_At_Coding signed main()
#if IDE
# pragma GCC optimize ("trapv")
#endif
#if OPTIMIZE
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,avx,avx2")
#endif
class dummy_ostream : public std::ostream {
public:
dummy_ostream():
std::ostream(&m_sb) {}
private:
class NullBuffer : public std::streambuf {
public:
int overflow(int c) { return c; }
} m_sb;
};
class redirect_ostream {
public:
redirect_ostream(ostream &_os):
os(_os) {}
template<class T>
redirect_ostream& operator << (const T &x) {
os << x;
return *this;
}
private:
ostream &os;
};
class dual_ostream {
public:
dual_ostream(ostream &_os1, ostream &_os2):
os1(_os1), os2(_os2) {}
template<class T>
dual_ostream& operator << (const T &x) {
os1 << x;
os2 << x;
return *this;
}
private:
ostream &os1, &os2;
};
#if IDE && !Interactive
# define Input fin
ifstream fin("cin.in");
ofstream fout("cout.out");
ofstream ferr("cerr.out");
dual_ostream Output(fout, cout);
dual_ostream Error(ferr, cerr);
#else
# define Input cin
redirect_ostream Output(cout);
# if IDE
redirect_ostream Error(cerr);
# else
dummy_ostream Error;
# endif
#endif
#define READ(a, t) t a; Input >> a
#define READARR(arr, n) REP(___i, 0, (n), 1) Input >> arr[___i];
#define PRINTARR(s, arr, n) { REP(___i, 0, (n), 1) s << arr[___i] << " "; s << endl; }
#define RI(a) READ(a, int)
#define RD(a) READ(a, double)
#define RC(a) READ(a, char)
#define RLL(a) READ(a, ll)
#define RSTR(a) READ(a, string)
#define RVI(__a, n) VI __a(n); READARR(__a, n)
#define RVLL(__a, n) VLL __a(n); READARR(__a, n)
#define RVSTR(__a, n) VSTR __a(n); READARR(__a, n)
#define randInt(l, r) uniform_int_distribution<int>(l, r-1)(rng)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll g[MAXN][MAXN];
ll g2[MAXN][MAXN];
ll profit[MAXN][MAXN];
ll B[MAXN][1000], S[MAXN][1000];
int N, M, K;
void floyd_warshall(ll g[MAXN][MAXN]) {
REPN(k, 0, N) REPN(i, 0, N) REPN(j, 0, N)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
void init() {
fill(g[0], g[MAXN-1]+MAXN, LINF);
Input >> N >> M >> K;
REPN(i, 0, N)
REPN(k, 0, K)
Input >> B[i][k] >> S[i][k];
REPN(i, 0, M) {
RI(a); RI(b); RI(c);
g[a-1][b-1] = c;
}
floyd_warshall(g);
REPN(i, 0, N) REPN(j, 0, N) REPN(k, 0, K)
if (B[i][k] != -1 and S[j][k] != -1)
profit[i][j] = max(profit[i][j], S[j][k] - B[i][k]);
}
bool check(ll m) {
REPN(i, 0, N) REPN(j, 0, N)
g2[i][j] = m * min(g[i][j], LINF/m) - profit[i][j];
floyd_warshall(g2);
REPN(i, 0, N) if (g2[i][i] <= 0) return true;
return false;
}
void solve() {
ll l = 0, r = INF;
while(l < r-1) {
ll mid = l+r >> 1;
if (check(mid)) l = mid;
else r = mid;
}
Output << l << endl;
}
I_Suck_At_Coding {
Foxyy
int T = 1;
// Input >> T;
while(T--) {
init();
solve();
}
}
Compilation message
merchant.cpp: In function 'void solve()':
merchant.cpp:152:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
152 | ll mid = l+r >> 1;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
1996 KB |
Output is correct |
2 |
Correct |
34 ms |
1228 KB |
Output is correct |
3 |
Correct |
44 ms |
1280 KB |
Output is correct |
4 |
Correct |
8 ms |
716 KB |
Output is correct |
5 |
Correct |
6 ms |
844 KB |
Output is correct |
6 |
Correct |
6 ms |
844 KB |
Output is correct |
7 |
Correct |
6 ms |
844 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
5 ms |
844 KB |
Output is correct |
10 |
Correct |
6 ms |
844 KB |
Output is correct |
11 |
Correct |
6 ms |
844 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
6 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
844 KB |
Output is correct |
2 |
Correct |
6 ms |
844 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
5 ms |
844 KB |
Output is correct |
5 |
Correct |
6 ms |
844 KB |
Output is correct |
6 |
Correct |
6 ms |
844 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
6 ms |
844 KB |
Output is correct |
9 |
Correct |
6 ms |
896 KB |
Output is correct |
10 |
Correct |
6 ms |
844 KB |
Output is correct |
11 |
Correct |
6 ms |
844 KB |
Output is correct |
12 |
Correct |
6 ms |
844 KB |
Output is correct |
13 |
Correct |
7 ms |
844 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
6 ms |
844 KB |
Output is correct |
16 |
Correct |
6 ms |
844 KB |
Output is correct |
17 |
Correct |
6 ms |
844 KB |
Output is correct |
18 |
Correct |
6 ms |
844 KB |
Output is correct |
19 |
Correct |
7 ms |
916 KB |
Output is correct |
20 |
Correct |
7 ms |
844 KB |
Output is correct |
21 |
Correct |
6 ms |
844 KB |
Output is correct |
22 |
Correct |
6 ms |
904 KB |
Output is correct |
23 |
Correct |
7 ms |
844 KB |
Output is correct |
24 |
Correct |
6 ms |
844 KB |
Output is correct |
25 |
Correct |
6 ms |
844 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
27 |
Correct |
7 ms |
920 KB |
Output is correct |
28 |
Correct |
7 ms |
844 KB |
Output is correct |
29 |
Correct |
9 ms |
844 KB |
Output is correct |
30 |
Correct |
9 ms |
800 KB |
Output is correct |
31 |
Correct |
6 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
844 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
7 ms |
920 KB |
Output is correct |
4 |
Correct |
7 ms |
844 KB |
Output is correct |
5 |
Correct |
9 ms |
844 KB |
Output is correct |
6 |
Correct |
9 ms |
800 KB |
Output is correct |
7 |
Correct |
6 ms |
844 KB |
Output is correct |
8 |
Correct |
42 ms |
1484 KB |
Output is correct |
9 |
Correct |
93 ms |
1992 KB |
Output is correct |
10 |
Correct |
38 ms |
1488 KB |
Output is correct |
11 |
Correct |
43 ms |
1612 KB |
Output is correct |
12 |
Correct |
45 ms |
1612 KB |
Output is correct |
13 |
Correct |
39 ms |
1484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
896 KB |
Output is correct |
2 |
Correct |
6 ms |
844 KB |
Output is correct |
3 |
Correct |
6 ms |
844 KB |
Output is correct |
4 |
Correct |
6 ms |
844 KB |
Output is correct |
5 |
Correct |
7 ms |
844 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
6 ms |
844 KB |
Output is correct |
8 |
Correct |
6 ms |
844 KB |
Output is correct |
9 |
Correct |
6 ms |
844 KB |
Output is correct |
10 |
Correct |
6 ms |
844 KB |
Output is correct |
11 |
Correct |
7 ms |
916 KB |
Output is correct |
12 |
Correct |
7 ms |
844 KB |
Output is correct |
13 |
Correct |
6 ms |
844 KB |
Output is correct |
14 |
Correct |
6 ms |
904 KB |
Output is correct |
15 |
Correct |
7 ms |
844 KB |
Output is correct |
16 |
Correct |
6 ms |
844 KB |
Output is correct |
17 |
Correct |
42 ms |
1484 KB |
Output is correct |
18 |
Correct |
93 ms |
1992 KB |
Output is correct |
19 |
Correct |
38 ms |
1488 KB |
Output is correct |
20 |
Correct |
43 ms |
1612 KB |
Output is correct |
21 |
Correct |
45 ms |
1612 KB |
Output is correct |
22 |
Correct |
39 ms |
1484 KB |
Output is correct |
23 |
Correct |
6 ms |
844 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
7 ms |
920 KB |
Output is correct |
26 |
Correct |
7 ms |
844 KB |
Output is correct |
27 |
Correct |
9 ms |
844 KB |
Output is correct |
28 |
Correct |
9 ms |
800 KB |
Output is correct |
29 |
Correct |
6 ms |
844 KB |
Output is correct |
30 |
Correct |
65 ms |
1996 KB |
Output is correct |
31 |
Correct |
34 ms |
1228 KB |
Output is correct |
32 |
Correct |
44 ms |
1280 KB |
Output is correct |
33 |
Correct |
8 ms |
716 KB |
Output is correct |
34 |
Correct |
6 ms |
844 KB |
Output is correct |
35 |
Correct |
6 ms |
844 KB |
Output is correct |
36 |
Correct |
6 ms |
844 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
5 ms |
844 KB |
Output is correct |
39 |
Correct |
6 ms |
844 KB |
Output is correct |
40 |
Correct |
6 ms |
844 KB |
Output is correct |
41 |
Correct |
1 ms |
460 KB |
Output is correct |
42 |
Correct |
6 ms |
844 KB |
Output is correct |
43 |
Correct |
37 ms |
1356 KB |
Output is correct |
44 |
Correct |
39 ms |
1612 KB |
Output is correct |
45 |
Correct |
59 ms |
2500 KB |
Output is correct |
46 |
Correct |
39 ms |
1476 KB |
Output is correct |
47 |
Correct |
39 ms |
1476 KB |
Output is correct |
48 |
Correct |
39 ms |
1568 KB |
Output is correct |
49 |
Correct |
98 ms |
3924 KB |
Output is correct |
50 |
Correct |
1 ms |
460 KB |
Output is correct |
51 |
Correct |
1 ms |
404 KB |
Output is correct |
52 |
Correct |
36 ms |
1336 KB |
Output is correct |
53 |
Correct |
38 ms |
1356 KB |
Output is correct |
54 |
Correct |
38 ms |
1356 KB |
Output is correct |
55 |
Correct |
37 ms |
1356 KB |
Output is correct |
56 |
Correct |
36 ms |
1228 KB |
Output is correct |
57 |
Correct |
1 ms |
332 KB |
Output is correct |
58 |
Correct |
8 ms |
972 KB |
Output is correct |
59 |
Correct |
8 ms |
1044 KB |
Output is correct |
60 |
Correct |
8 ms |
1048 KB |
Output is correct |
61 |
Correct |
100 ms |
4164 KB |
Output is correct |
62 |
Correct |
105 ms |
4056 KB |
Output is correct |
63 |
Correct |
1 ms |
332 KB |
Output is correct |