Submission #567732

#TimeUsernameProblemLanguageResultExecution timeMemory
567732shahriarkhanTravelling Merchant (APIO17_merchant)C++14
100 / 100
95 ms4284 KiB
#include<bits/stdc++.h> using namespace std ; const int MX_N = 105 , MX_K = 1005 ; const long long INF = 1e18 + 5 ; int n , m , k ; long long dist[MX_N][MX_N] , best[MX_N][MX_N] , buy[MX_N][MX_K] , sell[MX_N][MX_K] , profit[MX_N][MX_N] ; void floyd_warshall(long long dst[MX_N][MX_N]) { for(int l = 1 ; l <= n ; ++l) { for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= n ; ++j) { dst[i][j] = min(dst[i][j],dst[i][l]+dst[l][j]) ; } } } } int main() { scanf("%d%d%d",&n,&m,&k) ; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= k ; ++j) { scanf("%lld%lld",&buy[i][j],&sell[i][j]) ; } } for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= n ; ++j) { dist[i][j] = INF ; } } for(int i = 1 ; i <= m ; ++i) { long long v , w , t ; scanf("%lld%lld%lld",&v,&w,&t) ; dist[v][w] = t ; } floyd_warshall(dist) ; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= n ; ++j) { for(int l = 1 ; l <= k ; ++l) { if(buy[i][l]<0) continue ; if(sell[j][l]<0) continue ; best[i][j] = max(best[i][j],sell[j][l]-buy[i][l]) ; } } } long long low = 0 , high = 1e9 + 5 ; while(low<high) { long long mid = (low+high+1)/2 , good = 0 ; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= n ; ++j) { profit[i][j] = mid*min(INF/mid,dist[i][j]) - best[i][j] ; } } floyd_warshall(profit) ; for(int i = 1 ; i <= n ; ++i) { if(profit[i][i]<=0) good = 1 ; } if(good) low = mid ; else high = mid - 1 ; } printf("%lld\n",low) ; return 0 ; }

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d%d%d",&n,&m,&k) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             scanf("%lld%lld",&buy[i][j],&sell[i][j]) ;
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%lld%lld%lld",&v,&w,&t) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...