Submission #1117464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117464		thtsshz_bgwrswh	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	47 ms	2128 KiB

merchant

#include<stdio.h>
#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;
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]=1e12;
        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++){
                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*graph[i][j]-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:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%lld%lld%lld",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:22:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |             scanf("%lld%lld",&buy[i][j],&sell[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%lld%lld%lld",&u,&v,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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