Submission #1117463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117463		thtsshz_bgwrswh	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	48 ms	2248 KiB

merchant

#include<stdio.h>
#include<climits>
#include<algorithm>
using namespace std;
long long buy[105][1005],sell[105][1005];
long long graph[105][105],profit[105][105];
long long graph2[105][105];
long long n;
const long long INF = LLONG_MAX / 2;
void floyd(long long graph[105][105]){
    long long i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
}
int main(){
    long long i,j,m,k,l;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++)
            graph[i][j]=INF;
        for(j=0;j<k;j++){
            scanf("%lld%lld",&buy[i][j],&sell[i][j]);
        }
    }
    for(i=0;i<m;i++){
        long long u,v,c;
        scanf("%lld%lld%lld",&u,&v,&c);
        graph[u][v]=c;
    }
    floyd(graph);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            for(l=0;l<k;l++){
                if(sell[j][l]!=-1&&buy[i][l]!=-1)
                    profit[i][j]=max(profit[i][j],sell[j][l]-buy[i][l]);
            }
        }
    }
    long long left=0,right=1e9+1;
    while(right-left>1){
        long long mid = (right+left)/2;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                graph2[i][j]=mid*min(graph[i][j], INF/mid)-profit[i][j];
        floyd(graph2);
        bool check=0;
        for(i=1;i<=n;i++)
            check|=(graph2[i][i]<=0);
        if(check)
            left=mid;
        else
            right=mid;
    }
    printf("%lld",left);
}

Compilation message (stderr)

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

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