Submission #753475

#	Time	Username	Problem	Language	Result	Execution time	Memory
753475		karrigan	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	624 ms	4144 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
using pii=pair<int,int>;
using pli=pair<long long,int>;
const long long inf=1e18;
long long d[109][109];
long long b[109][1009];
long long s[109][1009];
bool ck[109][109];
long long f[109][109];
int n,m,k;
bool check(long long mid){
        for1(i,1,n){
        for1(j,1,n){
        f[i][j]=-inf;
        }
        }
        for1(i,1,n){
        for1(j,1,n){
        if (ck[i][j]||i==j)continue;
        long long cost=0;
        for1(l,1,k){
        if (b[i][l]==-1||s[j][l]==-1)continue;
        cost=max(cost,s[j][l]-b[i][l]);
        }
        cost=cost-d[i][j]*mid;
        f[i][j]=max(f[i][j],cost);
        }
        }
        for1(l,1,n){
        for1(i,1,n){
        for1(j,1,n){
        f[i][j]=max(f[i][j],f[i][l]+f[l][j]);
        }
        }
        }
        for1(i,1,n){
        if (f[i][i]>=0)return true;
        }
        return false;
}
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    cin>>n>>m>>k;
    for1(i,1,n){
    for1(j,1,n){
    d[i][j]=inf;
    }
    d[i][i]=0;
    }
    for1(i,1,n){
    for1(j,1,k){
    cin>>b[i][j]>>s[i][j];
    }
    }
    for1(i,1,m){
    int u,v;
    long long w;
    cin>>u>>v>>w;
    d[u][v]=min(d[u][v],w);
    }
    for1(z,1,n){
    for1(x,1,n){
    for1(y,1,n){
    d[x][y]=min(d[x][y],d[x][z]+d[z][y]);
    }
    }
    }
    for1(i,1,n){
    for1(j,1,n){
    ck[i][j]=(d[i][j]==inf);
    }
    }
    long long l1=1,r1=1e10,ans=0;
    while (l1<=r1){
        long long mid=(l1+r1)/2;
        if (check(mid)){
            l1=mid+1;
            ans=mid;
        }
        else r1=mid-1;
    }
    cout<<ans;
 
}

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