제출 #501139

#제출 시각아이디문제언어결과실행 시간메모리
501139Stickfish여행하는 상인 (APIO17_merchant)C++17
100 / 100
228 ms5884 KiB
#include <iostream> #include <cassert> #include <vector> using namespace std; using ll = __int128; const ll INF = 1.77013e15; const int MAXN = 100; const int MAXK = 1000; ll buy[MAXN][MAXK]; ll sell[MAXN][MAXK]; ll d[MAXN][MAXN]; ll prof[MAXN][MAXN]; ll smoke[MAXN][MAXN]; signed main() { int n, m, k; cin >> n >> m >> k; for (int i = 0; i < n; ++i) { for (int j = 0; j < k; ++j) { long long b, s; cin >> b >> s; buy[i][j] = b; sell[i][j] = s; //cin >> buy[i][j] >> sell[i][j]; if (buy[i][j] == -1) buy[i][j] = INF; if (sell[i][j] == -1) sell[i][j] = 0; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { d[i][j] = INF; } d[i][i] = 0; } for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; --u, --v; d[u][v] = w; } for (int i = 0; i < n; ++i) { for (int v = 0; v < n; ++v) { for (int u = 0; u < n; ++u) { d[v][u] = min(d[v][u], d[v][i] + d[i][u]); } } } //for (int i = 0; i < n; ++i) { //for (int j = 0; j < n; ++j) //cout << d[i][j] << ' '; //cout << endl; //} for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int w = 0; w < n; ++w) { assert(d[i][j] + d[j][w] >= d[i][w]); } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int t = 0; t < k; ++t) { prof[i][j] = max(prof[i][j], sell[j][t] - buy[i][t]); } } assert(prof[i][i] == 0); } //cout << endl; //for (int i = 0; i < n; ++i) { //for (int j = 0; j < n; ++j) //cout << prof[i][j] << ' '; //cout << endl; //} ll lb = 0, ub = INF; while (ub - lb > 1) { ll mb = (lb + ub) / 2; // (sum prof) / (sum time) >= mb // sum prof >= mb * (sum time) // sum {prof - mb * time} >= 0 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (d[i][j] == INF || j == i) smoke[i][j] = -INF; else smoke[i][j] = prof[i][j] - mb * d[i][j]; } } for (int i = 0; i < n; ++i) { for (int v = 0; v < n; ++v) { if (smoke[v][i] == -INF) continue; for (int u = 0; u < n; ++u) { if (smoke[i][u] == -INF) continue; smoke[v][u] = max(smoke[v][u], smoke[v][i] + smoke[i][u]); } } } //if (mb == 2) { //cout << endl; //for (int i = 0; i < n; ++i) { //for (int j = 0; j < n; ++j) { //if (smoke[i][j] == -INF) //cout << "-i "; //else //cout << smoke[i][j] << ' '; //} //cout << endl; //} //} bool isok = false; for (int i = 0; i < n; ++i) { if (smoke[i][i] >= 0) { isok = true; break; } } if (isok) lb = mb; else ub = mb; } cout << (long long)(lb) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...