제출 #630187

#제출 시각아이디문제언어결과실행 시간메모리
630187Shreyan_Paliwal여행하는 상인 (APIO17_merchant)C++17
0 / 100
84 ms2004 KiB
#include <bits/stdc++.h> using namespace std; using T = long long; const int maxn = 100; const int maxk = 1000; const int maxm = 9900; const T INF = 0x3fff'ffff'ffff'ffff; int n, m, k; // n markets, m pathways, k items T items[maxn][maxk][2]; // n markets, k items per market, buy/sell = price of buy/sell T grid[maxn][maxn]; // adj matrix T streaks[maxn][maxn]; T temp_streaks[maxn][maxn]; int main() { cin.tie(nullptr)->ios::sync_with_stdio(false); // freopen("main.in", "r", stdin); cin >> n >> m >> k; for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) for (int l = 0; l < 2; l++) cin >> items[i][j][l]; fill(&grid[0][0], &grid[0][0] + sizeof(grid) / sizeof(grid[0][0]), INF); for (int i = 0; i < m; i++) { int a, b; T c; cin >> a >> b >> c; a--, b--; grid[a][b] = min(grid[a][b], c); } // floyd warshall on grid for (int l = 0; l < n; l++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) grid[i][j] = min(grid[i][j], grid[i][l] + grid[l][j]); // creating streaks for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int l = 0; l < k; l++) if (items[j][l][1] != -1 && items[i][l][0] != -1) streaks[i][j] = max(streaks[i][j], items[j][l][1] - items[i][l][0]); // bin search on answer T lo = 0, hi = maxk * 1e9; while (lo < hi) { T mid = (lo + hi + 1) >> 1; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) temp_streaks[i][j] = streaks[i][j] - mid * grid[i][j]; for (int i = 0; i < n; i++) temp_streaks[i][i] = -INF; for (int l = 0; l < n; l++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) temp_streaks[i][j] = max(temp_streaks[i][j], temp_streaks[i][l] + temp_streaks[l][j]); bool works = false; for (int i = 0; i < n && !works; i++) works |= temp_streaks[i][i] >= 0; if (works) lo = mid; else hi = mid - 1; } // output cout << lo << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...