제출 #567456

#제출 시각아이디문제언어결과실행 시간메모리
567456hoanghq2004여행하는 상인 (APIO17_merchant)C++14
100 / 100
112 ms4244 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 1e2 + 10; const long long INF = 2e18 + 7; int n, m, k; int d[N][N]; long long w[N][N], f[N]; int p[N][N]; int B[N][N * N], S[N][N * N]; int check(int limit) { for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) w[i][j] = 1LL * limit * d[i][j] - p[i][j]; for (int k = 1; k <= n; ++k) { for (int u = 1; u <= n; ++u) for (int v = 1; v <= n; ++v) w[u][v] = min(w[u][v], w[u][k] + w[k][v]); for (int u = 1; u <= n; ++u) for (int v = u + 1; v <= n; ++v) if (w[u][v] + w[v][u] <= 0) return 1; } return 0; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for (int i = 1; i <= n; ++i) for (int j = 1; j <= k; ++j) cin >> B[i][j] >> S[i][j]; for (int u = 1; u <= n; ++u) for (int v = 1; v <= n; ++v) { for (int i = 1; i <= k; ++i) if (S[v][i] != -1 && B[u][i] != -1) p[u][v] = max(p[u][v], S[v][i] - B[u][i]); } for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) d[i][j] = (i == j ? 0 : 1e9 + 7); while (m--) { int u, v, w; cin >> u >> v >> w; d[u][v] = min(d[u][v], w); } for (int w = 1; w <= n; ++w) for (int u = 1; u <= n; ++u) for (int v = 1; v <= n; ++v) d[u][v] = min(d[u][v], d[u][w] + d[w][v]); int L = 0, R = 1e9 + 7; while (L < R) { int mid = L + R + 1 >> 1; if (check(mid)) L = mid; else R = mid - 1; } cout << L; }

컴파일 시 표준 에러 (stderr) 메시지

merchant.cpp: In function 'int main()':
merchant.cpp:62:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mid = L + R + 1 >> 1;
      |                   ~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...