Submission #230036

#TimeUsernameProblemLanguageResultExecution timeMemory
230036MetBTravelling Merchant (APIO17_merchant)C++14
0 / 100
387 ms1016 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define N 1000003 using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const ll INF = 1e15, MOD = INF + 7, MOD2 = 1e6 + 3; ll un_dist[100][100], deal[100][100]; ll sell[100][100], buy[100][100], n, m, k; ld d[100][100]; bool check (int x) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (un_dist[i][j] == INF) d[i][j] = -INF; else d[i][j] = (ld) deal[i][j] - (ld) x * un_dist[i][j]; } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (d[i][j] < d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j]; for (int i = 0; i < n; i++) if (d[i][i] >= 0) return true; return false; } int main () { cin >> n >> m >> k; for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) { int b, s; cin >> buy[i][j] >> sell[i][j]; } for (int i = 0; i < n; i++) fill (un_dist[i], un_dist[i] + n, (ll) INF); for (int i = 0; i < m; i++) { int u, v, l; cin >> u >> v >> l; u--, v--; un_dist[u][v] = min ((ll) l, un_dist[u][v]); } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) un_dist[i][j] = min (un_dist[i][j], un_dist[i][k] + un_dist[k][j]); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int it = 0; it < k; it++) if (sell[j][it] > 0 && buy[i][it] > 0) deal[i][j] = max (deal[i][j], sell[j][it] - buy[i][it]); int l = 1, r = 1e9; while (l < r) { int mid = (l + r + 1) / 2; if (check (mid)) l = mid; else r = mid - 1; } cout << l << endl; }

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:44:8: warning: unused variable 'b' [-Wunused-variable]
    int b, s;
        ^
merchant.cpp:44:11: warning: unused variable 's' [-Wunused-variable]
    int b, s;
           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...