Submission #406978

#	Time	Username	Problem	Language	Result	Execution time	Memory
406978		Waratpp123	Travelling Merchant (APIO17_merchant)	C++14	33 / 100	106 ms	2116 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
long long buy[105][1005],sell[105][1005],dis[105][105],prof[105][105],eff[105][105];
int main(){
    long long i,j,n,m,k,p,u,v,w,l,r,mid;
    scanf("%lld %lld %lld",&n,&m,&p);
    for(i=1;i<=n;i++){
        for(j=1;j<=p;j++){
            scanf("%lld %lld",&buy[i][j],&sell[i][j]);
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            dis[i][j]=2e18;
            prof[i][j]=0;
        }
    }
    for(i=1;i<=m;i++){
        scanf("%lld %lld %lld",&u,&v,&w);
        dis[u][v]=w;
    }
    for(k=1;k<=n;k++){
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(dis[i][j]>1e18){
                prof[i][j]=-1;
                continue;
            }
            int ch=0;
            for(k=1;k<=p;k++){
                if(sell[j][k]!=-1&&buy[i][k]!=-1) ch=1,prof[i][j]=max(prof[i][j],sell[j][k]-buy[i][k]);
            }
            if(ch==0) prof[i][j]=-1;
        }
    }
    l=0,r=1e9;
    while(l<r){
        mid=(l+r+1)/2;
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(prof[i][j]==-1) eff[i][j]=-1e18;
                else eff[i][j]=prof[i][j]-mid*dis[i][j];
            }
        }
        for(k=1;k<=n;k++){
            for(i=1;i<=n;i++){
                for(j=1;j<=n;j++){
                    if(prof[i][j]==-1) continue;
                    eff[i][j]=max(eff[i][j],eff[i][k]+eff[k][j]);
                }
            }
        }
        int ch=0;
        for(i=1;i<=n;i++) if(eff[i][i]>=0) ch=1;
        if(ch==1) l=mid;
        else r=mid-1;
    }
    printf("%lld\n",l);
return 0;
}

Compilation message (stderr)

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

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