제출 #977525

#제출 시각아이디문제언어결과실행 시간메모리
977525Halym2007여행하는 상인 (APIO17_merchant)C++17
100 / 100
108 ms1720 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define pii pair <ll, ll> #define ff first #define ss second #define sz size() // bir subtaska gecenson long long etmeli yerleri long long et INF-ny uly sana denle const int N = 1e2 + 5; const int K = 1e3 + 5; int buy[N][K], sell[N][K], n, m, d; ll val[N][N], dis[N][N], profit[N][N]; vector <ll> nodes; vector <pii> v[N]; ll INF = 1e13; ll node, new_jog; bool check (ll 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; } val[i][i] = -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 (ll i = 1; i <= n; ++i) { if (val[i][i] >= 0) return 1; } return 0; } int main () { // freopen ("input.txt", "r", stdin); cin >> n >> m >> d; for (ll i = 1; i <= n; ++i) { for (ll 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; } dis[i][i] = 0; } for (int i = 1; i <= m; ++i) { ll l, r, w; cin >> l >> 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 (buy[i][k] != -1 and sell[j][k] != -1) profit[i][j] = max (profit[i][j], sell[j][k] - 0LL - buy[i][k]); } } } ll l = 1, r = 1e9, jog = 0; ll sana = 0; while (l <= r) { ll 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:80:5: warning: unused variable 'sana' [-Wunused-variable]
   80 |  ll 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...