Submission #549874

#	Time	Username	Problem	Language	Result	Execution time	Memory
549874		FEDIKUS	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	145 ms	2568 KiB

merchant

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn=110;
const ll maxk=1010;
const ll inf=LLONG_MAX/2;

ll n,m,k;

ll b[maxn][maxk];
ll s[maxn][maxk];
ll gt[maxn][maxn];
ll gp[maxn][maxn];
ll checkg[maxn][maxn];

void init(){
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) gt[i][j]=inf;
}

void floyd(ll g[maxn][maxn]){
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            for(ll l=0;l<n;l++){
                g[j][l]=min(g[j][l],g[j][i]+g[i][l]);
            }
        }
    }
}

bool check(ll eff){
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            checkg[i][j]=inf;
            if(gt[i][j]==inf) continue;
            checkg[i][j]=eff*gt[i][j]-gp[i][j];
        }
    }
    floyd(checkg);
    for(ll i=0;i<n;i++){
        if(checkg[i][i]<=0) return true;
    }
    return false;
}

int main(){
    cin>>n>>m>>k;
    init();
    for(ll i=0;i<n;i++){
        for(ll j=0;j<k;j++) cin>>b[i][j]>>s[i][j];
    }
    for(ll i=0;i<m;i++){
        ll v,w,t;
        cin>>v>>w>>t;
        v--,w--;
        gt[v][w]=min(t,gt[v][w]);
    }
    floyd(gt);
    
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            for(ll l=0;l<k;l++){
                if(s[j][l]==-1 || b[i][l]==-1) continue;
                gp[i][j]=max(gp[i][j],s[j][l]-b[i][l]);
            }
        }
    }
    ll l=0,r=1e9+10,res=-1;
    while(l<=r){
        ll mid=(l+r)/2;
        if(check(mid)){
            res=mid;
            l=mid+1;
        }else r=mid-1;
    }
    cout<<res;
    return 0;
}

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