Submission #567709

#	Time	Username	Problem	Language	Result	Execution time	Memory
567709		shahriarkhan	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	714 ms	3376 KiB

merchant

#include<bits/stdc++.h>
using namespace std ;

const int MX_N = 105 , MX_K = 1005 ;

const long long INF = 1e9 + 5 ;

long long dist[MX_N][MX_N] , best[MX_N][MX_N] , buy[MX_N][MX_K] , sell[MX_N][MX_K] ;

pair<long long , long long> profit[MX_N][MX_N] ;

pair<long long , long long> f(pair<long long , long long> x , pair<long long , long long> y)
{
    if((x.first*y.second)>(y.first*x.second)) return x ;
    else if((x.first*y.second)<(y.first*x.second)) return y ;
    else if(x.first>y.first) return x ;
    else return y ;
}

int main()
{
    int n , m , k ;
    pair<long long , long long> ans = {0,0} ;
    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 ;
            profit[i][j] = {0,0} ;
        }
        dist[i][i] = 0 ;
    }
    for(int i = 1 ; i <= m ; ++i)
    {
        long long v , w , t ;
        scanf("%lld%lld%lld",&v,&w,&t) ;
        dist[v][w] = t ;
    }
    for(int l = 1 ; l <= n ; ++l)
    {
        for(int i = 1 ; i <= n ; ++i)
        {
            for(int j = 1 ; j <= n ; ++j)
            {
                if(dist[i][l]==INF) continue ;
                if(dist[l][j]==INF) continue ;
                dist[i][j] = min(dist[i][j],dist[i][l]+dist[l][j]) ;
            }
        }
    }
    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]) ;
            }
            profit[i][j] = {best[i][j],dist[i][j]} ;
        }
    }
    for(int x = 1 ; x <= n ; ++x)
    {
        for(int y = 1 ; y <= n ; ++y)
        {
            for(int i = 1 ; i <= n ; ++i)
            {
                for(int j = 1 ; j <= n ; ++j)
                {
                    profit[i][j] = f(profit[i][j],{profit[i][x].first + profit[x][y].first + profit[y][j].first , profit[i][x].second + profit[x][y].second + profit[y][j].second}) ;
                }
            }
        }
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= n ; ++j)
        {
            ans = f(ans,{profit[i][j].first,profit[i][j].second+dist[j][i]}) ;
        }
    }
    printf("%lld\n",ans.first/ans.second) ;
    return 0 ;
}

Compilation message (stderr)

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

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