Submission #567731

#	Time	Username	Problem	Language	Result	Execution time	Memory
567731		shahriarkhan	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	1094 ms	4116 KiB

merchant

#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)/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) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34