제출 #554159

#제출 시각아이디문제언어결과실행 시간메모리
554159status_coding여행하는 상인 (APIO17_merchant)C++14
100 / 100
150 ms4304 KiB
#include <iostream> #pragma GCC optimize ("unroll-loops") using namespace std; long long n,m,k; long long dist[105][105]; long long buy[105][1005], sell[105][1005]; long long prof[105][105]; long long profMax[105][105]; void calcDist() { for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } void calcProf() { for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { prof[i][j] = 0; for(int nr=1; nr<=k; nr++) if(buy[i][nr] != -1 && sell[j][nr] != -1) prof[i][j] = max(prof[i][j], sell[j][nr] - buy[i][nr]); } } bool ok(long long x) { long long inf = 1e18; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) profMax[i][j] = x * min(dist[i][j], inf / x) - prof[i][j]; for(int k=1; k<=n; k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) profMax[i][j] = min(profMax[i][j], profMax[i][k] + profMax[k][j]); for(int i=1;i<=n;i++) if(profMax[i][i] <= 0) return true; return false; } int main() { cin>>n>>m>>k; for(int i=1; i<=n; i++) for(int j=1; j<=k; j++) cin>>buy[i][j]>>sell[i][j]; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dist[i][j] = 1e18; for(int i=1; i<=m; i++) { long long x, y, w; cin>>x>>y>>w; dist[x][y] = min(dist[x][y], w); } calcDist(); calcProf(); long long st=1, dr=1e9, mij, last=0; while(st <= dr) { mij = (st+dr)/2; if(ok(mij)) { last = mij; st = mij+1; } else dr = mij-1; } cout<<last; 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...