# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
711351 | 2023-03-16T17:11:09 Z | ssense | 여행하는 상인 (APIO17_merchant) | C++17 | 82 ms | 4304 KB |
#include <bits/stdc++.h> #define startt ios_base::sync_with_stdio(false);cin.tie(0); typedef long long ll; using namespace std; #define vint vector<int> #define all(v) v.begin(), v.end() #define MOD 1000000007 #define MOD2 998244353 #define MX 1000000000 #define MXL 1000000000000000000 #define PI (ld)2*acos(0.0) #define pb push_back #define sc second #define fr first #define int long long #define endl '\n' #define ld long double #define NO cout << "NO" << endl #define YES cout << "YES" << endl int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu int n, m, k; vector<vector<pair<int, int>>> a; const int N = 105; int times[N][N]; int best[N][N]; int best2[N][N]; bool get(int r) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { best2[i][j] = best[i][j]-r*times[i][j]; } best2[i][i] = -MX; } for(int bruh = 1; bruh <= n; bruh++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { best2[i][j] = max(best2[i][j], best2[i][bruh] + best2[bruh][j]); } } } for(int i = 1; i <= n; i++) { if(best2[i][i] >= 0) { return true; } } return false; } void solve() { cin >> n >> m >> k; a.assign(n+5, vector<pair<int, int>>(k, {-1, -1})); for(int i = 0; i <= n; i++) { for(int j = 0; j <= n; j++) { times[i][j] = MX; } times[i][i] = 0; } for(int i = 1; i <= n; i++) { for(int j = 0; j < k; j++) { cin >> a[i][j].fr >> a[i][j].sc; } } for(int i = 0; i < m; i++) { int u, w, t; cin >> u >> w >> t; times[u][w] = t; } for(int bruh = 1; bruh <= n; bruh++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { times[i][j] = min(times[i][j], times[i][bruh] + times[bruh][j]); } } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(times[i][j] != MX) { for(int bruh = 0; bruh < k; bruh++) { if(a[j][bruh].sc != -1 && a[i][bruh].fr != -1) { best[i][j] = max(best[i][j], a[j][bruh].sc-a[i][bruh].fr); } } } else { best[i][j] = -MX; } } } int l = 0, r = 1000000000; while(l <= r) { int mid = l+r>>1; if(get(mid)) { l = mid+1; } else { r = mid-1; } } cout << r << endl; } int32_t main(){ startt int t = 1; //cin >> t; while (t--) { solve(); } } /* 4 5 2 10 9 5 2 6 4 20 15 9 7 10 9 -1 -1 16 11 1 2 3 2 3 3 1 4 1 4 3 1 3 1 1 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 2132 KB | Output is correct |
2 | Correct | 33 ms | 468 KB | Output is correct |
3 | Correct | 31 ms | 468 KB | Output is correct |
4 | Correct | 5 ms | 340 KB | Output is correct |
5 | Correct | 5 ms | 424 KB | Output is correct |
6 | Correct | 5 ms | 340 KB | Output is correct |
7 | Correct | 5 ms | 472 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 5 ms | 428 KB | Output is correct |
10 | Correct | 5 ms | 332 KB | Output is correct |
11 | Correct | 6 ms | 432 KB | Output is correct |
12 | Correct | 1 ms | 328 KB | Output is correct |
13 | Correct | 6 ms | 460 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 340 KB | Output is correct |
2 | Correct | 5 ms | 472 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 5 ms | 428 KB | Output is correct |
5 | Correct | 5 ms | 332 KB | Output is correct |
6 | Correct | 6 ms | 432 KB | Output is correct |
7 | Correct | 1 ms | 328 KB | Output is correct |
8 | Correct | 6 ms | 460 KB | Output is correct |
9 | Correct | 5 ms | 480 KB | Output is correct |
10 | Correct | 4 ms | 468 KB | Output is correct |
11 | Correct | 5 ms | 504 KB | Output is correct |
12 | Correct | 5 ms | 468 KB | Output is correct |
13 | Correct | 5 ms | 468 KB | Output is correct |
14 | Correct | 0 ms | 340 KB | Output is correct |
15 | Correct | 7 ms | 468 KB | Output is correct |
16 | Correct | 5 ms | 468 KB | Output is correct |
17 | Correct | 5 ms | 468 KB | Output is correct |
18 | Correct | 5 ms | 468 KB | Output is correct |
19 | Correct | 5 ms | 468 KB | Output is correct |
20 | Correct | 5 ms | 468 KB | Output is correct |
21 | Correct | 5 ms | 468 KB | Output is correct |
22 | Correct | 5 ms | 468 KB | Output is correct |
23 | Correct | 7 ms | 576 KB | Output is correct |
24 | Correct | 7 ms | 456 KB | Output is correct |
25 | Correct | 6 ms | 544 KB | Output is correct |
26 | Correct | 1 ms | 340 KB | Output is correct |
27 | Correct | 5 ms | 472 KB | Output is correct |
28 | Correct | 5 ms | 468 KB | Output is correct |
29 | Correct | 6 ms | 468 KB | Output is correct |
30 | Correct | 5 ms | 468 KB | Output is correct |
31 | Correct | 5 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 544 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 5 ms | 472 KB | Output is correct |
4 | Correct | 5 ms | 468 KB | Output is correct |
5 | Correct | 6 ms | 468 KB | Output is correct |
6 | Correct | 5 ms | 468 KB | Output is correct |
7 | Correct | 5 ms | 468 KB | Output is correct |
8 | Correct | 36 ms | 724 KB | Output is correct |
9 | Correct | 75 ms | 1936 KB | Output is correct |
10 | Correct | 33 ms | 728 KB | Output is correct |
11 | Correct | 41 ms | 956 KB | Output is correct |
12 | Correct | 36 ms | 852 KB | Output is correct |
13 | Correct | 36 ms | 708 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 480 KB | Output is correct |
2 | Correct | 4 ms | 468 KB | Output is correct |
3 | Correct | 5 ms | 504 KB | Output is correct |
4 | Correct | 5 ms | 468 KB | Output is correct |
5 | Correct | 5 ms | 468 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 7 ms | 468 KB | Output is correct |
8 | Correct | 5 ms | 468 KB | Output is correct |
9 | Correct | 5 ms | 468 KB | Output is correct |
10 | Correct | 5 ms | 468 KB | Output is correct |
11 | Correct | 5 ms | 468 KB | Output is correct |
12 | Correct | 5 ms | 468 KB | Output is correct |
13 | Correct | 5 ms | 468 KB | Output is correct |
14 | Correct | 5 ms | 468 KB | Output is correct |
15 | Correct | 7 ms | 576 KB | Output is correct |
16 | Correct | 7 ms | 456 KB | Output is correct |
17 | Correct | 36 ms | 724 KB | Output is correct |
18 | Correct | 75 ms | 1936 KB | Output is correct |
19 | Correct | 33 ms | 728 KB | Output is correct |
20 | Correct | 41 ms | 956 KB | Output is correct |
21 | Correct | 36 ms | 852 KB | Output is correct |
22 | Correct | 36 ms | 708 KB | Output is correct |
23 | Correct | 6 ms | 544 KB | Output is correct |
24 | Correct | 1 ms | 340 KB | Output is correct |
25 | Correct | 5 ms | 472 KB | Output is correct |
26 | Correct | 5 ms | 468 KB | Output is correct |
27 | Correct | 6 ms | 468 KB | Output is correct |
28 | Correct | 5 ms | 468 KB | Output is correct |
29 | Correct | 5 ms | 468 KB | Output is correct |
30 | Correct | 64 ms | 2132 KB | Output is correct |
31 | Correct | 33 ms | 468 KB | Output is correct |
32 | Correct | 31 ms | 468 KB | Output is correct |
33 | Correct | 5 ms | 340 KB | Output is correct |
34 | Correct | 5 ms | 424 KB | Output is correct |
35 | Correct | 5 ms | 340 KB | Output is correct |
36 | Correct | 5 ms | 472 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
38 | Correct | 5 ms | 428 KB | Output is correct |
39 | Correct | 5 ms | 332 KB | Output is correct |
40 | Correct | 6 ms | 432 KB | Output is correct |
41 | Correct | 1 ms | 328 KB | Output is correct |
42 | Correct | 6 ms | 460 KB | Output is correct |
43 | Correct | 32 ms | 596 KB | Output is correct |
44 | Correct | 36 ms | 816 KB | Output is correct |
45 | Correct | 50 ms | 2388 KB | Output is correct |
46 | Correct | 45 ms | 780 KB | Output is correct |
47 | Correct | 34 ms | 844 KB | Output is correct |
48 | Correct | 34 ms | 816 KB | Output is correct |
49 | Correct | 82 ms | 4168 KB | Output is correct |
50 | Correct | 1 ms | 340 KB | Output is correct |
51 | Correct | 1 ms | 340 KB | Output is correct |
52 | Correct | 31 ms | 596 KB | Output is correct |
53 | Correct | 35 ms | 672 KB | Output is correct |
54 | Correct | 34 ms | 596 KB | Output is correct |
55 | Correct | 32 ms | 620 KB | Output is correct |
56 | Correct | 30 ms | 468 KB | Output is correct |
57 | Correct | 1 ms | 292 KB | Output is correct |
58 | Correct | 6 ms | 564 KB | Output is correct |
59 | Correct | 6 ms | 596 KB | Output is correct |
60 | Correct | 6 ms | 596 KB | Output is correct |
61 | Correct | 82 ms | 4304 KB | Output is correct |
62 | Correct | 82 ms | 4164 KB | Output is correct |
63 | Correct | 1 ms | 340 KB | Output is correct |