제출 #767484

#제출 시각아이디문제언어결과실행 시간메모리
767484dxz05여행하는 상인 (APIO17_merchant)C++17
0 / 100
47 ms1236 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define bpc(x) __builtin_popcount(x) #define bpcll(x) __builtin_popcountll(x) #define MP make_pair #define BIT(x, i) (((x) >> (i)) & 1) //#define endl '\n' mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); typedef long long ll; const int MOD = 1e9 + 7; const int N = 1e6 + 3e2; void solve(){ int n, m, items; cin >> n >> m >> items; vector<vector<int>> B(n, vector<int>(items, -1)); vector<vector<int>> S(n, vector<int>(items, -1)); const long long INF = 1e18; vector<vector<ll>> dist(n, vector<ll>(n, INF)); for (int i = 0; i < n; i++){ for (int j = 0; j < items; j++) cin >> B[i][j] >> S[i][j]; dist[i][i] = 0; } while (m--){ int u, v, w; cin >> u >> v >> w; --u, --v; dist[u][v] = w; } for (int k = 0; k < n; k++){ for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } vector<vector<int>> max_diff(n, vector<int>(n, 0)); for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ for (int k = 0; k < items; k++){ if (B[i][k] == -1 || S[j][k] == -1) continue; max_diff[i][j] = max(max_diff[i][j], S[j][k] - B[i][k]); } } } function<bool(ll)> check = [&](ll val) -> bool{ vector<vector<ll>> d(n, vector<ll>(n, -INF)); for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ if (i == j) continue; d[i][j] = max_diff[i][j] - val * dist[i][j]; if (d[i][j] < 0) d[i][j] = -INF; } d[i][i] = 0; } for (int k = 0; k < n; k++){ for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ d[i][j] = max(d[i][j], d[i][k] + d[k][j]); } } } for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ if (i == j) continue; ll cur = d[i][j] + max_diff[j][i] - val * dist[j][i]; if (cur >= 0) return true; } } return false; }; ll l = 0, r = 1e9; while (l <= r){ ll mid = (l + r) >> 1; if (check(mid)){ l = mid + 1; } else { r = mid - 1; } } cout << l - 1 << endl; } int main(){ clock_t startTime = clock(); ios_base::sync_with_stdio(false); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int test_cases = 1; // cin >> test_cases; for (int test = 1; test <= test_cases; test++){ // cout << (solve() ? "YES" : "NO") << endl; solve(); } #ifdef LOCAL cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl; #endif return 0; }

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

merchant.cpp: In function 'int main()':
merchant.cpp:106:13: warning: unused variable 'startTime' [-Wunused-variable]
  106 |     clock_t startTime = clock();
      |             ^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...