Submission #241391

#	Time	Username	Problem	Language	Result	Execution time	Memory
241391		nafis_shifat	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	141 ms	2296 KiB

merchant

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=101;
const ll inf=1e10+6;
const ll inf2=1e13;
const int mxk=1001;

int n;
ll b[mxn][mxk],s[mxn][mxk];
ll g[mxn][mxn];
ll pr[mxn][mxn];

ll adj[mxn][mxn];
bool check(ll d) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            adj[i][j]=d*g[i][j]-max(0ll,pr[i][j]);
            adj[i][j]=min(adj[i][j],inf2);
        }
        
        adj[i][i]=inf;
    }
    for(int k=1;k<=n;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++)
       if(adj[i][i]<=0) {
           return true;
       }
    return false;  
    
       
}

int main() {
    int m,k;
    cin>>n>>m>>k;
    
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=k;j++) {
            scanf("%lld",&b[i][j]);
            scanf("%lld",&s[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
           g[i][j]=inf;
    
    for(int i=1;i<=m;i++) {
        int u,v;ll w;
        scanf("%d%d%lld",&u,&v,&w);
        g[u][v]=w;
    }
    
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            pr[i][j]=-inf;
            for(int x=1;x<=k;x++) {
                if(s[j][x]!=-1 && b[i][x]!=-1)
                   pr[i][j]=max(pr[i][j],s[j][x]-b[i][x]);
            }
        }
    }
    
    for(int l=1;l<=n;l++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                g[i][j]=min(g[i][j],g[i][l]+g[l][j]); 
            }
        }
    }
    
    
    int lo=1;
    int hi=1e9+2;
    
   
    int ans=0;
    while(lo<=hi) {
        int mid=lo+hi>>1;
        if(check(mid)) {
            ans=mid;
            lo=mid+1;
        } else {
            hi=mid-1;
        }
    }
    
    cout<<ans<<endl;
    
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:85:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=lo+hi>>1;
                 ~~^~~
merchant.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld",&b[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~
merchant.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld",&s[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~
merchant.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%lld",&u,&v,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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