Submission #402770

#	Time	Username	Problem	Language	Result	Execution time	Memory
402770		Hazem	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	109 ms	5168 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 2e5+10;
const int M = 200;
const LL INF = 1e9;
const LL LINF = 1e14;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

LL s[M][M*10],b[M][M*10];
LL dis[M][M],profit[M][M],dis1[M][M];

int main(){

    //freopen("out.txt","w",stdout);

    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
            scanf("%lld%lld",&b[i][j],&s[i][j]);

    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        dis[u][v] = w;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!dis[i][j])
                dis[i][j] = LINF;

    for(int k1=1;k1<=n;k1++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j] = min(dis[i][j],dis[i][k1]+dis[k1][j]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int j1=1;j1<=k;j1++)
                if(b[i][j1]!=-1&&s[j][j1]!=-1)
                    profit[i][j] = max(profit[i][j],s[j][j1]-b[i][j1]);

    LL l = 0,r = 1e9;
    while(l<r){

        int mid = (l+r+1)/2;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dis[i][j]!=LINF)
                    dis1[i][j] = dis[i][j]*mid-profit[i][j];
                else 
                    dis1[i][j] = LINF;
        
        for(int k1=1;k1<=n;k1++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    dis1[i][j] = min(dis1[i][j],dis1[i][k1]+dis1[k1][j]);

        bool q = 0;
        for(int i=1;i<=n;i++)
            q |= dis1[i][i]<=0;

        if(q)l = mid;
        else r = mid-1;
    }

    printf("%lld\n",l);
}   

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     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",&b[i][j],&s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d%d%d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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