Submission #532267

#	Time	Username	Problem	Language	Result	Execution time	Memory
532267		Fidisk	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	108 ms	4196 KiB

merchant

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll oo=1e9;
const ll maxans=1e9;

ll n,m,k,buys[109][1009],sell[109][1009],cost[109][109],dist[109][109],f[109][109],u,v,w,ans,i,j,l;

bool ok(ll x) {
    for (ll ii=1;ii<=n;ii++) {
        for (ll ij=1;ij<=n;ij++) {
            f[ii][ij]=cost[ii][ij]-dist[ii][ij]*x;
        }
    }
    for (ll ii=1;ii<=n;ii++) {
        for (ll ij=1;ij<=n;ij++) {
            for (ll jj=1;jj<=n;jj++) {
                f[ij][jj]=max(f[ij][jj],f[ij][ii]+f[ii][jj]);
            }
        }
    }
    for (ll ii=1;ii<=n;ii++) {
        if (f[ii][ii]>=0) {
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    for (i=1;i<=n;i++) {
        for (j=1;j<=k;j++) {
            cin>>buys[i][j];
            cin>>sell[i][j];
        }
    }
    for (i=1;i<=n;i++) {
        for (j=1;j<=n;j++) {
            dist[i][j]=oo;
        }
    }
    for (i=1;i<=m;i++) {
        cin>>u>>v>>w;
        dist[u][v]=w;
    }
    for (i=1;i<=n;i++) {
        for (j=1;j<=n;j++) {
            for (l=1;l<=n;l++) {
                dist[j][l]=min(dist[j][l],dist[j][i]+dist[i][l]);
            }
        }
    }
    for (i=1;i<=n;i++) {
        for (j=1;j<=n;j++) {
            for (l=1;l<=k;l++) {
                if (buys[i][l]!=-1) {
                    if (sell[j][l]!=-1) {
                        cost[i][j]=max(cost[i][j],sell[j][l]-buys[i][l]);
                    }
                }
            }
        }
    }
    /*
    for (i=1;i<=n;i++) {
        for (j=1;j<=n;j++) {
            cout<<dist[i][j]<<' ';
        }
        cout<<'\n';
    }
    for (i=1;i<=n;i++) {
        for (j=1;j<=n;j++) {
            cout<<cost[i][j]<<' ';
        }
        cout<<'\n';
    }
    */
    ans=0;
    for (i=maxans;i>0;i/=2) {
        while (ok(ans+i)) {
            ans+=i;
        }
    }
    cout<<ans<<'\n';
}

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