Submission #230167

#	Time	Username	Problem	Language	Result	Execution time	Memory
230167		mehrdad_sohrabi	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	127 ms	4216 KiB

merchant

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
/// khodaya komak kon
/// ya navid navid
const int N=110,K=1010,inf=(ll)1e18;
ll g[N][N];
ll val[N][N];
ll b[N][K],s[N][K];
ll dp[N][N];
ll n,m,k1;
ll check(ll mid){
    for (int i=0;i<N;i++) for (int j=0;j<N;j++) dp[i][j]=-(ll)1e12;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (g[i][j]==0 || inf/g[i][j]<mid) continue;
            dp[i][j]=val[i][j]-g[i][j]*mid;
        }
    }
    /*
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (dp[i][j]>=0){
                cout << mid << " " << i << " " << j << " kjernkfin " << endl;
            }
        }
    }
    */
    for (int k=1;k<=n;k++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]);
                dp[i][j]=min(dp[i][j],inf);
            }
        }
    }
    for (int i=1;i<=n;i++) if (dp[i][i]>=0) return 1;
    return 0;
}
int32_t main(){
    sync;
    cin >> n >> m >> k1;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=k1;j++){
            cin >> b[i][j] >> s[i][j] ;
        }
    }
    for (int i=0;i<N;i++) for (int j=0;j<N;j++) g[i][j]=(ll)1e12;
    for (int i=1;i<=n;i++) g[i][i]=0;
    for (int i=0;i<m;i++){
        ll v,u,w;
        cin >> v >> u >> w;
        g[v][u]=min(g[v][u],w);
    }
    for (int k=1;k<=n;k++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            for (int k=1;k<=k1;k++){
                if (b[i][k]==-1 || s[j][k]==-1) continue;
                val[i][j]=max(val[i][j],-b[i][k]+s[j][k]);
            }
        }
    }
    /*
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
          //  cout << i << " " << j << " " << g[i][j] << " " << val[i][j] << endl;
        }
    }
    */
    ll l=0,r=1e9+100;
    while(r-l>1){
          //  cout << r << " " << l << endl;
        ll mid=(r+l)/2;
        if (check(mid)) l=mid;
        else r=mid;
    }
    cout << l << endl;
}

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