제출 #977311

#제출 시각아이디문제언어결과실행 시간메모리
977311Halym2007여행하는 상인 (APIO17_merchant)C++17
0 / 100
73 ms2732 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define pii pair <int, int> #define ff first #define ss second #define sz size() // bir subtaska gecenson long long etmeli yerleri long long et dis-y uly sana denle const int N = 1e2 + 5; const int K = 1e3 + 5; int val[N][N], buy[N][K], sell[N][K], n, m, d, dis[N][N], profit[N][N]; vector <int> nodes; vector <pii> v[N]; int INF = 1e8; int node, new_jog; bool check (int x) { // jog - x * time >= 0 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (dis[i][j] != INF) val[i][j] = profit[i][j] - x * dis[i][j]; else val[i][j] = -INF; } } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { val[i][j] = max (val[i][j], val[i][k] + val[k][j]); } } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i == j) continue; if (dis[i][j] != 1e8 and dis[j][i] != 1e8) if (val[i][j] + val[j][i] >= 0) { return 1; } } } return 0; } int main () { // freopen ("input.txt", "r", stdin); cin >> n >> m >> d; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= d; ++j) { cin >> buy[i][j] >> sell[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dis[i][j] = INF; if (i == j) dis[i][j] = 0; } } for (int i = 1; i <= m; ++i) { int l, r, w; cin >> l >> r >> w; v[l].pb ({r, w}); dis[l][r] = w; } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dis[i][j] = min (dis[i][j], dis[i][k] + dis[k][j]); } } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i == j) continue; for (int k = 1; k <= d; ++k) { // k-th item-y i-njiden satyn alyan j-nynjyda satyan if (sell[j][k] != -1 and buy[i][k] != -1) profit[i][j] = max (profit[i][j], sell[j][k] - buy[i][k]); } } } // cout << check(2); // return 0; int l = 0, r = INF, jog = 0; int sana = 0; while (l <= r) { int md = (l + r) / 2; if (check (md)) { jog = md; l = md + 1; } else { r = md - 1; } } cout << jog; }

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

merchant.cpp: In function 'int main()':
merchant.cpp:87:6: warning: unused variable 'sana' [-Wunused-variable]
   87 |  int sana = 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...